#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int num[50005];
int best[50005];
int CURR=0;
bool same(int x){
int temp=Query(x);
int res=CURR==temp;
CURR=temp;
return res;
}
int n;
vector<int> v; //singles
vector<ii> v2; //pairs
int B;
map<int,int> pos;
struct node{
int len;
vector<int> l; //indices
node *L=nullptr,*R=nullptr;
node (int _len){
len=_len;
if (len==1){
l={v.back()}; v.pob();
}
else if (len==2 && !v2.empty()){
l={v2.back().fi,v2.back().se}; v2.pob();
}
else{
L=new node(best[len]);
R=new node(len-best[len]);
for (auto it:L->l) l.pub(it);
for (auto it:R->l) l.pub(it);
}
}
void solve(vector<int> r,bool in){
if (L==nullptr){
if (sz(r)==2){
if (pos[r[0]]<B){
Answer(l[0],r[0]);
Answer(l[1],r[1]);
return;
}
else{
v=l;
L=new node(1);
R=new node(1);
}
}
else{
Answer(l[0],r[0]);
return;
}
}
for (auto it:L->l) same(it);
vector<int> r1,r2;
for (auto it:r){
if (sz(L->l)==sz(r1)) r2.pub(it);
else if (sz(R->l)==sz(r2)) r1.pub(it);
else if (same(it) != in) r1.pub(it);
else r2.pub(it);
}
L->solve(r1,!in);
R->solve(r2,in);
}
} *root;
vector<int> get(vector<int> inp){
vector<int> temp,r;
rep(x,0,sz(inp)){
if (same(inp[x])) r.pub(inp[x]);
else temp.pub(inp[x]);
}
vector<int> l,oth;
for (auto it:temp){
if (same(it)) l.pub(it);
else oth.pub(it);
}
B=max(0LL,sz(l)/4-5);
rep(x,0,B) v2.pub({l[x],l[sz(l)-1-x]});
rep(x,B,sz(l)-B) v.pub(l[x]);
root=new node(sz(l));
rep(x,0,sz(r)) pos[r[x]]=x;
root->solve(r,false);
return oth;
}
void Solve(signed N) {
num[1]=0;
rep(x,2,50005){
num[x]=1e9;
int l=max(1LL,(int)(x*0.25)),r=min(x,(int)(x*0.4)+2);
rep(y,l,r) if (num[x]>num[y]+num[x-y]+x+y){
num[x]=num[y]+num[x-y]+x+y;
best[x]=y;
}
}
n=N;
vector<int> idx;
rep(x,1,2*n+1) idx.pub(x);
shuffle(all(idx),rng);
vector<int> l,r;
rep(x,0,n) l.pub(idx[x]);
rep(x,n,2*n) r.pub(idx[x]);
l=get(l),r=get(r);
if (sz(l)==0) return;
v=l;
root=new node(sz(l));
root->solve(r,false);
}
