#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include "gap.h"
#define ll long long
#define MAXV 1e18
using namespace std;
long long solve1(int n)
{
ll ar[n];
ll curl = 1;
ll curh = n-2;
MinMax(0,MAXV,&ar[0],&ar[n-1]);
while(curl <= curh)
{
MinMax(ar[curl-1]+1,ar[curh+1]-1,&ar[curl],&ar[curh]);
curl++;
curh--;
}
ll dif = 0;
for(int i = 1;i < n;i++)
{
dif = max(dif,ar[i]-ar[i-1]);
}
return dif;
}
long long findGap(int T, int N)
{
if(T == 1)
return solve1(N);
long long a,b;
MinMax(0LL,MAXV,&a,&b);
ll dif = (b-a)/(N-1)-2;
ll k = 1;
while(a < b)
{
ll w,x;
MinMax(a+1,a+dif*k,&x,&w);
if(w == -1)
{
k++;
continue;
}
if(k != 1)
dif = max(dif,x-a);
k=1;
a = w;
}
return dif;
}
