#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
vector<long long> arr;
long long part1(int N)
{
long long mn = -1, mx = 1e18 + 2;
arr.resize(N);
int i = 0, j = N-1;
while(i <= j)
{
long long a = mn+1, b = mx-1;
if(a > b)
break;
MinMax(a, b, &mn, &mx);
arr[i] = mn;
arr[j] = mx;
i++;
j--;
}
long long max_diff = 0;
for(int i = 0; i < N-1; i++)
max_diff = max(max_diff, arr[i+1] - arr[i]);
return max_diff;
}
int idx = 0;
void aux(long long l, long long r, long long step)
{
long long mn = -1, mx = 1e18 + 2;
int i = 1;
while(l + step * i - 1 < r)
{
MinMax(l + step * (i-1), l + step * i - 1, &mn, &mx);
if(mn != -1) {
if(step == 1) {
arr[idx] = mn;
idx++;
}
else
aux(l + step * (i-1), l + step * i - 1, step / 1e6);
}
i++;
}
}
long long part2(int N)
{
arr.resize(N);
aux(0, 1e18, 1e12);
long long max_diff = 0;
for(int i = 0; i < N-1; i++)
max_diff = max(max_diff, arr[i+1] - arr[i]);
return max_diff;
}
long long findGap(int T, int N)
{
if(T == 1)
return part1(N);
else
return part2(N);
}
