#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()
ll solve1(int N){
vi A(N); ll L = 0, R = 1e18;
for(int l = 0, r = N-1; l <= r; l++, r--){
MinMax(L, R, &A[l], &A[r]);
L = A[l]+1, R = A[r]-1;
assert(A[l] != -1 and A[r] != -1);
}
ll ans = 0;
for(int x = 0; x < N-1; x++)
ans = max(ans, A[x+1]-A[x]);
return ans;
}
ll solve2(int N){
ll L, R; MinMax(0, 1e18, &L, &R);
ll D = (R-L+N-2)/(N-1);
for(ll K = L+1; K < R; ){
ll mn, mx; MinMax(K, K+D-1, &mn, &mx);
if(mx != -1){
K = mx+1; continue;
}
for(ll i = 2; ; i++){
MinMax(K, K+i*D-1, &mn, &mx);
if(mn == -1) continue;
D = mn-K+1; K = mx+1;
break;
}
}
return D;
}
ll findGap(int T, int N){
if(T == 1) return solve1(N);
return solve2(N);
}
