#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
set<ll> all_data;
vector<pair<ll,ll>> now_interval;
vector<pair<ll,ll>> next_interval;
ll mn,mx;
ll find_ans(){
ll answer = 0;
for(auto i = all_data.begin();i!=all_data.end();i++){
i++;
if(i!=all_data.end()){
ll check = *i; i--;
answer = max(answer, check - *i);
}
else break;
}
return answer;
}
ll findGap(int T, int N)
{
now_interval.push_back(make_pair(0,1e18));
while((int)now_interval.size()){
for(auto i:now_interval){
MinMax(i.first,i.second,&mn,&mx);
if(mn!=-1){
if(mn==mx) all_data.insert(mn);
else{
all_data.insert(mn);
all_data.insert(mx);
if((mx-mn)==1) next_interval.push_back(make_pair(mn+1,(mn+mx)/2));
else{
next_interval.push_back(make_pair(mn+1,(mn+mx)/2));
next_interval.push_back(make_pair((mn+mx)/2+1,mx-1));
}
}
}
}
now_interval=next_interval;
next_interval.clear();
}
return find_ans();
}
