#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#include "gap.h"
typedef long long ll;
vector<ll> a;
pair<ll,ll> qu(ll l, ll r){
ll mn = 1, mx = 1;
MinMax(l, r, &mn, &mx);
return {mn, mx};
}
long long findGap(int t, int n)
{
auto [l, r] = qu(0, 1e18);
ll len = (r-l) / (n-1);
ll ans = len;
ll pv = l;
while(r-pv > len){
auto [l_, r_] = qu(l, l+len);
if(l_ != -1){
ans = max(ans, l_ - pv);
pv = r_;
}
l += len+1;
}
return ans;
}
