#include "gap.h"
#include <deque>
#include <stack>
#include <algorithm>
using namespace std;
long long findGap(int T, int N)
{
long long a,b;
stack<long long> l;
stack<long long> r;
a = 0;
b = 1000000000000000000;
long long mn,mx;
int c = 0;
while (c*2<N){
MinMax(a,b,&mn,&mx);
c++;
if (mn<mx){
l.push(mn);
r.push(mx);
}
else if (mn==mx){
l.push(mn);
}
else break;
a = mn+1;
b = mx-1;
}
deque<long long> vals;
while (!l.empty()){
vals.push_front(l.top());
l.pop();
}
while (!r.empty()){
vals.push_back(r.top());
r.pop();
}
long long ans=0;
for (int x = 0; x<N-1; x++){
ans = max(ans,vals[x+1]-vals[x]);
}
return ans;
}
