#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
pair < long long, long long > ask(long long l, long long r)
{
if(l > r)return make_pair(-1, -1);
long long mn, mx;
MinMax(l, r, &mn, &mx);
return make_pair(mn, mx);
}
long long findGap(int T, int N)
{
if(T == 1)
{
long long l = 0, r = 1LL * 1e18;
vector < long long > g;
while(g.size() < N)
{
pair < long long, long long> curr = ask(l , r);
if(curr.first == -1)break;
l = curr.first;
r = curr.second;
g.push_back(l);
if(l != r)g.push_back(r);
else break;
l ++;
r --;
}
sort(g.begin(), g.end());
long long maxspace = 0;
assert((int)g.size() == N);
for (int i = 0; i < g.size()-1; ++ i)
{
long long space = 1LL * (g[i+1] - g[i]);
maxspace = max(maxspace, space);
}
return maxspace;
}
pair < long long, long long > initial = ask(1LL * 0, 1LL * 1e18);
long long l = initial.first, r = initial.second;
long long sz = N, len;
vector < long long > g;
g.push_back(l);
len = r - l;
long long ans = 0;
long long range = max(1LL * 1, (len) / (sz-1));
long long last = l;
while(l < r)
{
pair < long long , long long > values = ask(l + 1, l + range);
if(values.first != -1)
{
sz --;
ans = max(ans, values.first - last);
last = values.second;
}
l = l + 1 + range;
}
long long maxspace = 0;
return ans;
}
