#include <bits/stdc++.h>
#include "gap.h"
/*
Chang ki si xuyen man dem
Di lac vao trong giac mong
*/
using namespace std;
using ll = long long;
// #define int long long
#define pii pair<ll, ll>
#define fi first
#define se second
const ll inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19;
pii blk[500005];
//static void my_assert(int k){ if (!k) exit(1); }
//
//static int subtask_num, N;
//static long long A[100001];
//static long long call_count;
//
//void MinMax(long long s, long long t, long long *mn, long long *mx)
//{
// int lo = 1, hi = N, left = N+1, right = 0;
// my_assert(s <= t && mn != NULL && mx != NULL);
// while (lo <= hi){
// int mid = (lo+hi)>>1;
// if (A[mid] >= s) hi = mid - 1, left = mid;
// else lo = mid + 1;
// }
// lo = 1, hi = N;
// while (lo <= hi){
// int mid = (lo+hi)>>1;
// if (A[mid] <= t) lo = mid + 1, right = mid;
// else hi = mid - 1;
// }
// if (left > right) *mn = *mx = -1;
// else{
// *mn = A[left];
// *mx = A[right];
// }
// if (subtask_num == 1) call_count++;
// else if (subtask_num == 2) call_count += right-left+2;
//}
ll findGap(int t, int n) {
ll ans = 0;
if (t == 1) {
deque <ll> dq;
int l = 1, r = n;
ll curL = 0, curR = inf + 1;
while(l <= r) {
MinMax(curL + 1, curR - 1, &curL, &curR);
l++; r--;
dq.push_front(curL);
dq.push_back(curR);
}
vector <ll> val;
while(dq.size()) {
val.push_back(dq.front());
dq.pop_front();
}
sort(val.begin(), val.end());
for (int i = 1; i < val.size(); i++) {
ans = max(ans, val[i] - val[i - 1]);
}
// for (int i = 0; i < val.size(); i++) cout << val[i] << ' ';
}
else {
ll curL = 1, curR = inf;
MinMax(curL, curR, &curL, &curR);
// cout << curL << ' ' << curR << '\n';
ll sz = (curR - curL + 1) / (n - 1); // size cua 1 block
ll cur = 0;
for (int i = curL; i <= curR; i += sz) {
cur++;
MinMax(i, i + sz - 1, &blk[cur].fi, &blk[cur].se);
}
for (int i = 1; i <= cur; i++) ans = max(ans, blk[i].se - blk[i].fi);
for (int i = 2; i <= cur; i++) ans = max(ans, blk[i].fi - blk[i - 1].se);
}
return ans;
}
//signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
// if (fopen(".inp", "r")) {
// freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
// }
// int t;
// cin >> t >> N;
// for (int i = 1; i <= N; i++) cin >> A[i];
// subtask_num = t;
// cout << findGap(t, N);
// return 0;
//}
