#include <bits/stdc++.h>
#include "grader.h"
int query(vector<int> v);
int n;
mt19937 rnd(23232);
bool yey[300];
void solve(int N){
n=N;
vector<int>perm;
for(int q=1;q<=n;q++){
perm.push_back(q);
}
while(true){
shuffle(perm.begin(),perm.end(),rnd);
if(query(perm)==0)break;
}
// cout<<"PERM"<<endl;
// for(auto x : perm){
// cout<<x<<" ";
// }
// cout<<endl;
int benar=0,prv=0;
while(true){
vector<int>slh;
for(int q=0;q<n;q++){
if(!yey[q]){
slh.push_back(q);
}
}
if(slh.empty())break;
vector<int>tmp;
while(true){
tmp=perm;
shuffle(slh.begin(),slh.end(),rnd);
for(int q=1;q<slh.size();q+=2){
swap(tmp[slh[q-1]],tmp[slh[q]]);
}
int apa=query(tmp);
if(apa==n)return;
if(apa>prv)break;
}
// for(auto x : slh){
// cout<<x<<" ";
// }
// cout<<endl;
int l=0,r=slh.size()/2;
int brp=0;
while(l<=r){
int mid=(l+r)/2;
tmp=perm;
for(int q=0;q<mid;q++){
swap(tmp[slh[2*q]],tmp[slh[2*q+1]]);
}
int apa=query(tmp);
if(apa==n)return;
if(apa>prv){
brp=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
brp--;
int a=slh[2*brp],b=slh[2*brp+1];
swap(perm[a],perm[b]);
int tot=query(perm);
if(tot==n)return;
if(tot-prv==2){
yey[a]=yey[b]=true;
benar=a;
prv=tot;
continue;
}
if(benar){
tmp=perm;
swap(tmp[a],tmp[benar]);
int apa=query(tmp);
if(apa==n)return;
if(apa==tot-1){
yey[b]=true;
}
else{
yey[a]=true;
}
prv=tot;
}
else{
int lain=1;
while(lain==a || lain==b)lain++;
tmp=perm;
swap(tmp[lain],tmp[b]);
int apa=query(tmp);
if(apa==n)return;
if(apa<tot){
yey[b]=true;
benar=b;
}
else{
yey[a]=true;
benar=a;
}
prv=tot;
}
}
}
