#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
const int N=1e5+10;
long long a[N];
long long findGap(int t,int n){
    if(t==1){
        int l=1,r=n;
        a[0]=-1,a[n+1]=(long long)1e18+1;
        while(l<=r){
            long long x,y;
            MinMax(a[l-1]+1,a[r+1]-1,&x,&y);
            a[l]=x,a[r]=y;
            l++,r--;
        }long long ans=0;
        for(int i=2;i<=n;i++) ans=max(ans,a[i]-a[i-1]);
        return ans;
    }else{
        MinMax(0,1e18,&a[1],&a[n]);
        long long B=(a[n]-a[1]+n-2)/(n-1);
        long long la=a[1],bl=a[1],ans=0;
        while(bl<a[n]){
            long long x,y;
            MinMax(bl+1,bl+B,&x,&y);
            bl+=B;
            if(x==-1||y==-1) continue;
            ans=max(ans,x-la);
            la=y;
        }return max(ans,a[n]-la);
    }
    
}