#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
int N;
ll A[MAXN];
ll findGap (int subtask, int nnn) {
N = nnn;
ll ans = 0;
if (subtask == 1) {
for (int i = 1, j = N; i <= j; i++, j--) {
ll mn, mx;
if (i == 1) {
mn = 0;
mx = 1e18;
} else {
mn = A[i - 1] + 1;
mx = A[j + 1] - 1;
}
MinMax(mn, mx, &mn, &mx);
A[i] = mn;
A[j] = mx;
}
for (int i = 2; i <= N; i++) {
ans = max(ans, A[i] - A[i - 1]);
}
} else {
ll a1, an;
MinMax(0, 1e18, &a1, &an);
ll gap = (an - a1 + (N - 2)) / (N - 1); //gap at least this big
ll pval = a1;
for (ll lt = a1 + 1, rt = a1 + gap; lt <= an; lt += gap, rt += gap) {
ll imn, imx; //interval mn, mx
MinMax(lt, rt, &imn, &imx);
if (imn != -1) {
ans = max(ans, imn - pval);
pval = imx;
}
}
ans = max(ans, an - pval);
}
return ans;
}
