#include "gap.h"
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
long long findGap(int T, int N)
{
ll ans = 1;
ll st, end;
MinMax(1, 1e18, &st, &end);
if(T==2){
ll len = end-st;
ll gap = (len+N-2)/(N-1);
ans = max(gap, ans);
vl arr = {st};
ll ff = st+1, ss = st+1+gap;
ll one, two;
while(ff<=end){
MinMax(ff, ss, &one, &two);
if(one!=-1) arr.push_back(one);
if(two!=-1) arr.push_back(two);
ff += gap+1, ss += gap+1;
}
for(int i = 1; i < arr.size(); i++){
ans = max(ans, arr[i]-arr[i-1]);
}
}else{
vl ff = {st}, ss = {end};
st++, end--;
while(st<=end){
ll mn, mx;
MinMax(st, end, &mn, &mx);
ff.push_back(mn);
ss.push_back(mx);
st = mn+1, end = mx-1;
}
for(int i = ss.size()-1; i >= 0; i--) ff.push_back(ss[i]);
for(int i = 1; i < ff.size(); i++) ans= max(ans, ff[i]-ff[i-1]);
}
return ans;
}
