#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
const long long MX = 1000000000000000000;
long long mn, mx;
int n;
long long findGap(int t, int N) {
n = N;
if (t == 1) {
long long left, right;
left = 0;
right = MX;
vector<long long> arr1, arr2;
for (int i = 0; i < (n + 1) / 2; i++) {
MinMax(left, right, &mn, &mx);
arr1.push_back(mn);
arr2.push_back(mx);
left = mn + 1;
right = mx - 1;
}
long long ans = arr2.back() - arr1.back();
for (int i = 0; i < (int)arr1.size() - 1; i++) {
ans = max(ans, arr1[i + 1] - arr1[i]);
ans = max(ans, arr2[i] - arr2[i + 1]);
}
return ans;
}
MinMax(0, MX, &mn, &mx);
long long left = mn;
long long right = mx;
long long delta = (mx - mn + n - 2) / (n - 1);
vector<long long> pos;
pos.push_back(left);
for (int i = 0; i < n - 1; i++) {
MinMax(left + i * delta + 1, min(left + (i + 1) * delta, right), &mn, &mx);
if (mn != -1) {
pos.push_back(mn);
pos.push_back(mx);
}
}
pos.push_back(right);
long long ans = 0;
for (int i = 0; i < (int)pos.size(); i++) {
ans = max(ans, pos[i + 1] - pos[i]);
}
return ans;
}
