#include <bits/stdc++.h>
#include "grader.h"
#define pb push_back
using namespace std;
#define F first
#define sz size()
#define S second
#define in insert
#define all(v) v.begin(), v.end()
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)
#define FORR(x, n, m, d) for(int x = n; x >= m; x -= d)
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);
const int N = 300+5;
int n,m,k,tt,ans,sum=0,l, r, x, y, cnt, block = 448, res;
int a[N][N], b[N], c[N];
vector<int>q, v, lp;
void solve(int n){
FOR(i, 1, n, 1)q.pb(i);
while(1){
random_shuffle(all(q));
ans = query(q);
if(ans==n)return;
if(!ans)break;
}
cnt = 0;
vector<pair<int, int>>par;
vector<int>unknown;
FOR(i, 2, n, 1){
swap(q[0], q[i-1]);
sum = query(q);
if(sum==n)return;
if(sum==2){
b[1] = b[i] = 1;
ans+=2;
break;
}
if(sum==1)v.pb(i);
swap(q[0], q[i-1]);
}
for(auto i : v){
swap(q[i-1], q[0]);
if(i != 2)swap(q[0], q[1]);
else swap(q[0], q[2]);
k = query(q);
if(k == n)return;
if(k == 0){
b[1] = 1;
if(i != 2)swap(q[0], q[1]);
else swap(q[0], q[2]);
ans++;
break;
}
}
while(cnt != n){
par.clear();
unknown.clear();
FOR(i,1,n,1){
if(!b[i])unknown.pb(i);
}
while(1){
random_shuffle(all(unknown));
FOR(i, 1, unknown.sz-1, 2)swap(q[unknown[i]-1], q[unknown[i-1]-1]);
sum = query(q);
if(sum==n)return;
if(sum>ans)break;
FOR(i, 1, unknown.sz-1, 2)swap(q[unknown[i]-1], q[unknown[i-1]-1]);
}
FOR(i, 1, unknown.sz-1, 2)par.pb({ unknown[i]-1, unknown[i-1]-1 });
l = 0, r = par.sz-1;
res = 0;
while(l <= r){
int md = (l + r) >> 1;
FOR(i, md+1, r, 1){
swap(q[par[i].S], q[par[i].F]);
}
sum = query(q);
if(sum==n)return;
if(sum == ans){
FOR(i, md+1, r, 1){
swap(q[par[i].S], q[par[i].F]);
}
FOR(i, l, md, 1)swap(q[par[i].S], q[par[i].F]);
l = md + 1;
}
else r = md - 1, res = md;
}
swap(q[0], q[par[res].F]);
sum = query(q);
if(sum==n)return;
if(sum == ans - 2)cnt++, b[par[res].F] = 1, ans++;
swap(q[0], q[par[res].F]);
swap(q[0], q[par[res].S]);
sum = query(q);
if(sum == n)return;
if(sum == ans - 2)cnt++, b[par[res].S] = 1, ans++;
swap(q[0], q[par[res].S]);
}
query(q);
}
