#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
pair < long long, long long > ask(long long l, long long r)
{
long long mn, mx;
MinMax(l, r, &mn, &mx);
return make_pair(mn, mx);
}
long long findGap(int T, int N)
{
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 + 1;
long long range = max(1LL * 1, (len + sz - 1) / (sz));
while(l < r)
{
pair < long long , long long > values = ask(l + 1, l + 1 + range);
if(values.first != -1 && values.second < r && values.second > l)
{
sz --;
g.push_back(values.first);
g.push_back(values.second);
///cout << "NOTICED " << values.second << endl;
l = values.second;
}
else l = l + 1 + range;
}
///cout << "finished " << endl;
g.push_back(r);
long long maxspace = 0;
for (int i = 0; i < g.size()-1; ++ i)
{
long long space = g[i+1] - g[i];
maxspace = max(maxspace, space);
}
return maxspace;
}
