#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

long long findGap(int T, int N)
{
	vector<ll> A(N);
	ll l=-1,r=N;
	rep(loop,(N+1)/2){
		if(loop==0){
			ll mn,mx;
			MinMax(0,1000000000000000000,&mn,&mx);
			l++,r--;
			A[l]=mn;
			A[r]=mx;
		}else{
			ll mn,mx;
			MinMax(A[l]+1,A[r]-1,&mn,&mx);
			l++,r--;
			A[l]=mn;
			A[r]=mx;
		}
	}
	ll ans=1000000000000000000;
	rep(i,N-1) ans=min(ans,A[i+1]-A[i]);
	return ans;
}