#include "gap.h"
#include "vector"
#include <cmath>
using namespace std;
long long findGap(int T, int N)
{ vector<long long>a(N);
long long i=0;
long long int hi=1e18,low=0;
if(T==1){
while(i<=(N-1)/2){
long long int s=low,t=hi;
MinMax(low,hi,&s,&t);
if(s==t){
if(s<0)continue;
a[i]=t;
break;
}
else{
a[i]=s;
low=s+1;
a[N-1-i]=t;
hi=t-1;
}
i++;
}
long long int x=0;
for(int k=0;k<N-1;k++){
if(x<(a[k+1]-a[k]))x=a[k+1]-a[k];
}
return x;
}
else{
long long int s,t;
MinMax(low,hi,&s,&t);
a[0]=s;
a[N-1]=t;
long long int x=1;
low=s+1;
while(x<=N/2){
MinMax(low,hi,&s,&t);
a[x]=s;
x++;
low=s+1;
}
low=0;
hi=t-1;
while(x<N-1){
MinMax(low,hi,&s,&t);
a[x]=t;
hi=t-1;
x++;
}
x=0;
for(int k=0;k<N-1;k++){
if(x<(a[k+1]-a[k]))x=a[k+1]-a[k];
}
return x;
}
}
