#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
long long findGap(int T, int n){
ll ans = 0;
if(T == 1){
vector<ll>a(n);
ll low = 0, high = 1e18;
int l = 0, r = n - 1;
while(l <= r){
MinMax(low, high, &a[l], &a[r]);
low = a[l++] + 1;
high = a[r--] - 1;
}
for(int i = 1; i < n; i++){
maximize(ans, a[i] - a[i - 1]);
}
}
else{
ll a_1, a_n;
MinMax(0, 1e18, &a_1, &a_n);
ll average = (a_n - a_1 + n - 2) / (n - 1);
while(true){
ll next_value = -1, temp, to = a_1;
while((to += average) < a_n && next_value == -1){
MinMax(a_1 + 1, to, &next_value, &temp);
}
maximize(ans, (next_value == -1 ? a_n : next_value) - a_1);
a_1 = temp;
if(next_value == -1){
break;
}
}
}
return ans;
}
