#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> ans;
map<vector<int>,int> m;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int myquery(vector<int> v,int f=0,int s=0)
{
vector<int> tmp=ans;
int pos=0;
for (int i:v)
{
while (tmp[pos])
pos++;
tmp[pos]=i;
}
swap(tmp[find(tmp.begin(),tmp.end(),f)-tmp.begin()],tmp[find(tmp.begin(),tmp.end(),s)-tmp.begin()]);
if (!m.count(tmp))
m[tmp]=query(tmp);
return m[tmp];
}
int go(int l,int r,vector<int> p)
{
if (l==r)
{
int pos=0;
for (int i=0;i<=l;i++)
{
while (ans[pos])
pos++;
if (i==l)
{
ans[pos]=p[l];
}
pos++;
}
return p[l];
}
if (l+1==r)
{
int t=1;
while (t==p[l] || t==p[r])
t++;
int a=myquery(p,p[l],t);
if (a==ans.size())
return -1;
int b=myquery(p,p[r],t);
if (b==ans.size())
return -1;
if (a<b)
return go(l,l,p);
return go(r,r,p);
}
int a=myquery(p);
if (a==ans.size())
return -1;
if (l+2==r)
{
int b=myquery(p,p[l],p[l+1]);
if (b==ans.size())
return -1;
if (a>b)
return go(l,l+1,p);
return go(r,r,p);
}
int mid=(l+r)/2;
for (int t=0;;t^=1)
{
vector<int> tmp=p;
int nl=l,nr=r;
if (t)
{
shuffle(tmp.begin()+l,tmp.begin()+mid+1,rng);
nr=mid;
}
else
{
shuffle(tmp.begin()+mid+1,tmp.begin()+r+1,rng);
nl=mid+1;
}
int b=myquery(tmp);
if (b==ans.size())
return -1;
if (a>b)
return go(nl,nr,p);
if (a<b)
return go(nl,nr,tmp);
}
}
void solve(int n)
{
ans=vector<int>(n,0);
vector<int> cur;
for (int i=1;i<=n;i++)
cur.push_back(i);
for (int i=1;i<n;i++)
{
while (1)
{
shuffle(cur.begin(),cur.end(),rng);
int a=myquery(cur);
if (a==ans.size())
return;
if (a>=i)
break;
}
int a=go(0,n-i,cur);
if (a==-1)
return;
cur.erase(find(cur.begin(),cur.end(),a));
}
myquery(cur);
}
