#include "gap.h"
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;
//1,3,5,8,10,12
LL findGap(int t, int n){
if (t==1){
set<LL> s;
LL mn=-1, mx=2e18;
while (mn<mx){
LL a=mn, b=mx;
MinMax(a+1,b-1,&mn,&mx);
if (mn!=-1) s.insert(mn);
if (mx!=-1) s.insert(mx);
if (SZ(s)==n) break;
}
vector<LL> v;
for (LL x:s) v.push_back(x);
LL ans=0;
FOR(i,n-1) ans=max(ans, v[i+1]-v[i]);
return ans;
}
else{
LL mn=0,mx=1e18;
MinMax(0,1e18,&mn,&mx);
LL diff=mx-mn;
LL gap=(diff+n-2)/(n-1);
LL t2=mn, ans=gap;
for (LL i=mn; i<=mx; i+=gap){
if (i==mx){
ans=max(ans,mx-t2);
continue;
}
LL t3=0,t4=0;
MinMax(i,min(i+gap-1,mx),&t3,&t4);
if (t3!=-1){
ans=max(ans, t3-t2);
t2=t4;
}
}
return ans;
}
}
