/**
* author: Vi Gia Huy
* Vi Gia Huy will win VOI 27
**/
#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
const long long INF = 1000000000000000000LL;
const int N = 1e5 + 6;
int n;
long long res;
namespace sub1 {
long long a[N];
long long mn;
long long mx;
void sol() {
a[0] = -1;
a[n + 1] = INF + 1;
int l = 1;
int r = n;
while (l <= r) {
MinMax(a[l - 1] + 1, a[r + 1] - 1, &mn, &mx);
a[l] = mn;
a[r] = mx;
l++;
r--;
}
res = 0;
for (int i = 1; i < n; i++) {
res = max(res, a[i + 1] - a[i]);
}
return;
}
}
namespace sub2 {
long long mn;
long long mx;
void sol() {
MinMax(0, INF, &mn, &mx);
long long l = (mx - mn + n - 2) / n - 1;
res = l;
long long premx = mn;
for (long long i = mn + 1; i < mx; i += l + 1) {
long long curmn;
long long curmx;
long long tmp = min(i + l, mx - 1);
MinMax(i, tmp, &curmn, &curmx);
if (curmn != -1) {
res = max(res, curmn - premx);
premx = curmx;
}
}
res = max(res, mx - premx);
return;
}
}
long long findGap(int _T, int _N) {
n = _N;
if (_T == 1) sub1::sol();
else sub2::sol();
return res;
}
