#include "gap.h"
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MIN = 0, MAX = 1000000000000000000;
ll solve1(int n) {
ll v[n+1];
int i = 1, k = n;
ll mn = MIN, mx = MAX;
while (i <= k) {
MinMax(mn, mx, v+i, v+k);
mn = v[i++]+1;
mx = v[k--]-1;
}
ll ret = 1;
for (int i = 1; i < n; i++)
ret = max(ret, v[i+1] - v[i]);
return ret;
}
ll solve2(int n) {
ll cur, lim;
MinMax(MIN, MAX, &cur, &lim);
ll ans = (lim - cur + 1)/n, test, l, r;
while (cur < lim && cur + ans < lim) {
test = ans + 2;
do {
MinMax(cur+1, cur+test, &l, &r);
test = test*2 + 2;
} while (l == -1);
ans = max(ans, l - cur);
cur = r;
}
return ans;
}
ll findGap(int t, int n)
{
return (t == 1 || n <= 8) ? solve1(n) : solve2(n);
}
