#include<bits/stdc++.h>
#include "light.h"
using namespace std;
#define int long long
int n;
vector<long long> prec;
void prepare()
{
n=1;
prec.clear();
prec.push_back(1);
}
int calc(vector<long long> aux)
{
int poz=0,mxm=0;
for(int i=0;i<aux.size();i++)
{
while(poz+1<prec.size() && prec[poz+1]<=aux[i])
poz++;
mxm = max(mxm, aux[i]-prec[poz]);
}
return mxm;
}
vector<long long> simplify(vector<long long> aux)
{
vector<long long> newaux;
for(int i=0;i<aux.size();i++)
if(i==0 || aux[i]!=aux[i-1])
newaux.push_back(aux[i]);
return newaux;
}
pair<long long, vector<long long>> join(long long p)
{
n += p;
vector<int> aux;
aux = prec;
aux.push_back(n);
for(int i=2;n-i+1>n-p;i*=2)
aux.push_back(n-i+1);
sort(aux.begin(),aux.end());
aux = simplify(aux);
int x = calc(aux);
prec=aux;
return {x, aux};
}
pair<long long, vector<long long>> leave(long long p)
{
n -= p;
vector<int> aux;
for(int i=prec.size()-1;i>=0;i--)
{
for(int j=0;j<=p;j++)
aux.push_back(min(n,prec[i]+j));
//aux.push_back(min(n,prec[i]));
}
sort(aux.begin(),aux.end());
aux = simplify(aux);
int x = calc(aux);
prec=aux;
return {x, aux};
}
