#include "gap.h"
#include <cstdio>
#include <algorithm>
#define ll long long
#define MAX_V (ll)1e18
using namespace std;
ll res;
long long findGap(int t, int n){
int i;
ll l, r, nl, nr, now, tmp;
MinMax(0ll, MAX_V, &l, &r);
if(t == 1){
n -= 2;
while(n > 0){
MinMax(l + 1, r - 1, &nl, &nr);
res = max(res, max(r - nr, nl - l));
l = nl; r = nr;
n -= 2;
}
res = max(res, r - l);
return res;
}
res = now = (r - l + (n - 2)) / (n - 1); nl = l;
for(i = 1; i < n; i++){
MinMax(l + now * (i - 1) + i, l + now * i + i, &nr, &tmp);
res = max(res, nr - nl);
if(tmp != -1) nl = tmp;
}
return res;
}
