// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
#include "gap.h"
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll INF = (ll)1e18;
ll subtask1(int n) {
ll l, r, ans = 0;
MinMax(0, INF, &l, &r);
int met = 2;
while (met < n) {
ll nl, nr;
MinMax(l + 1, r - 1, &nl, &nr);
ans = max(ans, nl - l);
ans = max(ans, r - nr);
l = nl;
r = nr;
met += 2;
}
ans = max(ans, r - l);
return ans;
}
ll subtask2(int n) {
ll ourL, ourR;
MinMax(0, INF, &ourL, &ourR);
ll A = (ourR - ourL + 1) / (n + 1);
ll B = (ourR - ourL + 1) % (n + 1);
ll ret = 0;
ll ptr = ourL;
vector<ll> L(n + 1), R(n + 1);
for (int i = 0; i <= n; ++i) {
ll cur = A + (i + B > n);
MinMax(ptr, ptr + cur - 1, &L[i], &R[i]);
ptr += cur;
}
ptr = -1;
for (int i = 0; i <= n; ++i) {
if (L[i] != -1) {
if (ptr != -1) {
ret = max(ret, L[i] - ptr);
}
ptr = R[i];
}
}
ptr = -1;
for (int i = n; i >= 0; --i) {
if (R[i] != -1) {
if (ptr != -1) {
ret = max(ret, ptr - R[i]);
}
ptr = L[i];
}
}
return ret;
}
ll findGap(int T, int N) {
if (T == 1) {
return subtask1(N);
}
else {
return subtask2(N);
}
}
