#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
using ll = long long;
using vll = vector<long long>;
ll solveST1(int n)
{
vll arr;
vll barr;
ll mn,mx;
ll p1=1;
ll p2=n;
ll lb=0;
ll ub=1000000000000000000ll;
while(p1<p2)
{
MinMax(lb,ub,&mn,&mx);
arr.push_back(mn);
barr.push_back(mx);
lb=mn+1;
ub=mx-1;
p1+=1;
p2-=1;
}
if(p1==p2)
{
MinMax(lb,ub,&mn,&mx);
arr.push_back(mn);
}
reverse(barr.begin(),barr.end());
for(auto num:barr)
arr.push_back(num);
ll ans=LONG_LONG_MIN;
for(int i=1;i<n;i++)
ans=max(ans,arr[i]-arr[i-1]);
return ans;
}
ll solveST2(int n)
{
return -1;
}
long long findGap(int T, int N)
{
ll ans=0;
if(T==1)
return solveST1(N);
else
return solveST1(N);
}
