#include <bits/stdc++.h>
#include "gap.h"
#define TASK "gap"
#define INT_LIM (int) 2147483647
#define LL_LIM (long long) 9223372036854775807
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define ll long long
#define pii pair<int,int>
using namespace std;
///------------------------------------------///
ll a[100005];
long long findGap(int T, int N)
{
if (T==1)
{
ll mn = 0, mx = 1e18;
FOR(i, 1, (N+1)/2)
{
ll newmin, newmax;
MinMax(mn, mx, &newmin, &newmax);
a[i] = newmin;
a[N-i+1] = newmax;
mn = newmin+1;
mx = newmax-1;
}
ll ret = 0;
FOR(i, 1, N-1)
{
ret = max(ret, a[i+1]-a[i]);
}
return ret;
}
ll n = N;
MinMax(0, 1e18, &a[1], &a[n]);
ll v = (a[n]-a[1]+(n-1)-1)/(n-1);
ll ret = 0, lastv = a[1];
for (ll l = a[1]+1; l<a[n]; l+=v)
{
ll r = l+v-1;
r = min(r, a[n]-1);
ll minr = -1, maxr = -1;
MinMax(l, r, &minr, &maxr);
if (minr!=-1)
{
ret = max(ret, minr-lastv);
}
if (maxr!=-1) lastv = maxr;
}
ret = max(ret, a[n]-lastv);
return ret;
}
//signed main()
//{
// ///--------------------------///
// ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// if (fopen(TASK".INP","r")!=NULL)
// {
// freopen(TASK".INP","r",stdin);
// freopen(TASK".OUT","w",stdout);
// }
// ///--------------------------///
//
// return 0;
//}
//
/////------------------------------------------///
