#include <bits/stdc++.h>
#include "gap.h"
#define f first
#define s second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
ll mas=0;
ll vv[100001];
int k=0;
int N;
void ric(ll a,ll b){
ll u,v;
MinMax(a,b,&u,&v);
if(u==-1&&v==-1)return;
if(u==v){vv[k++]=u;
return;}
if(v-u<15LL){
for(ll i=u;i<=v;i++)ric(i,i);
return;
}
ll m=(v-u)/15LL;
ric(u,u+m);
for(ll i=1LL;i<=(ll)(15-2);i++)ric(u+i*m+1LL,u+(i+1LL)*m);
ric(u+(ll)(15-1)*m+1,v);
}
int findGap(int T,int N){
::N=N;
if(T==2){
ll g=1;
for(int i=0;i<18;i++)g*=10LL;
ric(0LL,g);
for(int i=0;i<N;i++)mas=max(mas,vv[i+1]-vv[i]);
return mas;
}
ll a=0,b=1000000000000000000;
int i=0,j=N-1;
while(i<=j){
MinMax(a,b,&a,&b);
vv[i]=a;
vv[j]=b;
i++;
j--;
a++;
b--;
}
for(int i=0;i<N-1;i++)mas=max(mas,vv[i+1]-vv[i]);
return mas;
}
