#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long mx, mn, l, r;
vector<long long> arr;
long long findAns() {
long long ans = 0;
sort(arr.begin(), arr.end());
for(int i=0; i<arr.size()-1; i++) {
ans = max(ans, arr[i+1]-arr[i]);
}
return ans;
}
long long findGap(int T, int N) {
l=0; r=1e18;
if(T == 1) {
for(int i=1; i<=N/2; i++) {
MinMax(l, r, &mn, &mx);
if(mn == -1 || mx == -1) {
break;
}
arr.push_back(mn);
arr.push_back(mx);
l = mn+1;
r = mx-1;
}
if(N%2 == 1) {
MinMax(l, r, &mn, &mx);
arr.push_back(mn);
}
return findAns();
}
MinMax(l, r, &mn, &mx);
l = mn;
r = mx;
arr.push_back(mn);
arr.push_back(mx);
long long in = (r-l+N+1)/(N+1)+1;
if((r-l)/in > 1000000) return 0;
for(int j=l+1; j<r; j+=in) {
MinMax(j, j+in-1, &mn, &mx);
if(mn != -1 && mx != -1) {
arr.push_back(mn);
arr.push_back(mx);
}
}
return findAns();
}
