#include "gap.h"
#include <bits/stdc++.h>
#define ll long long
long long findGap(int T, int N)
{
std::vector<int> all;
if(N==2){
ll v1=0-1,v2=1e18+1;
MinMax(v1+1,v2-1,&v1,&v2);
return v2-v1;
}
if(T==1){
std::vector<ll> left;
std::vector<ll> right;
ll v1=0-1,v2=1e18+1;
while(left.size()+right.size()<N&&v1!=v2){
MinMax(v1+1,v2-1,&v1,&v2);
// std::cout << v1+1 << ' ' << v2-1 << '\n';
if(v1==-1 || v2==-1)break;
left.push_back(v1);
right.push_back(v2);
all.push_back(v1);all.push_back(v2);
}
// ll best=0;
// for(int i=0;i<left.size()-1;i++){
// ll diff = left[i+1]-left[i];
// best=std::max(diff,best);
// }
// for(int i=0;i<right.size()-1;i++){
// ll diff = right[i]-right[i+1];
// best=std::max(diff,best);
// }
// // std::cout << '\n';
// // for(int i=0;i<left.size();i++){
// // std::cout << left[i] << ' ';
// // }
// // for(int i=right.size()-1;i>=0;i--){
// // std::cout << right[i] << ' ';
// // }
// // std::cout << '\n';
// best=std::max(best,right.back()-left.back());
// return best;
}
else{
ll v1=0-1,v2=1e18+1,high=0,low=0;
MinMax(v1+1,v2-1,&v1,&v2);
all.push_back(v1);all.push_back(v2);
high=v2;low=v1;
ll dis = v2-v1;
ll meandis = (dis/N) + 1;
ll test1 =v1+1,test2 = v1+meandis;
ll last=v1;
ll best = 0;
while(test1<high){
MinMax(test1,test2,&v1,&v2);
if(v1!=-1)
best=std::max((ll)best,v1-last);
if(v2!=-1)
last=v2;
all.push_back(v1);all.push_back(v2);
//best=std::max(best,v2-v1);// not really needed
test1+=meandis;
test2+=meandis;
}
}
int ans=0;
sort(all.begin(),all.end());
for(int i = 0;i < all.size()-1;i++) ans = std::max(ans,all[i+1]-all[i]);
return ans;
}
