#include <bits/stdc++.h>
#include "puzzle.h"
using namespace std;
mt19937 zsh(20070610);
typedef pair<int,int> pr;
vector<pr> q;
vector<int> E[1010];
int n,hfn,x,y;
vector<int> ans,tk,rd;
int clc(vector<pr> &q)
{
	tk=rd;
	for(pr g:q) swap(tk[g.first],tk[g.second]);
	return query(tk);
}
void solve(vector<pr> &q,int cnt)
{
	if(!cnt) return;
	if(q.size()==1)
	{
		E[q[0].first].push_back(q[0].second);
		E[q[0].second].push_back(q[0].first);
		return;
	}
	vector<pr> L,R;int mid=q.size()>>1,tmp;
	for(int i=0;i<mid;i++) L.push_back(q[i]);
	for(int i=mid,lm=q.size();i<lm;i++) R.push_back(q[i]);
	tmp=clc(L);
	solve(L,tmp),solve(R,cnt-tmp);
}
bool vis[1010];
int stk[1010],top,ls;
void dfs(int a)
{
	vis[a]=true,stk[++top]=a;
	for(int v:E[a]) if(!vis[v])
		dfs(v);
}
void play(int n)
{
	::n=n;
	rd.resize(n);
	for(int i=0;i<n;i++) rd[i]=i;

	if(n<=5)
	{
		do if(query(rd)==n) return check(rd);
		while(next_permutation(rd.begin(),rd.end()));
	}

	while(1)
	{
		for(int i=1;i<n;i++) swap(rd[i],rd[zsh()%(i+1)]);
		if(!query(rd)) break;
	}

	hfn=n>>1;
	for(int i=0;i<n;i++)
	{
		vector<pr>().swap(q);
		if((n&1)||i<hfn) x=i,y=i+1;
		else x=y=i;
		while(y>=n) y-=n;
		for(int j=0;j<hfn;j++)
		{
			if(x!=y&&E[x].size()<=1&&E[y].size()<=1)
				q.push_back(make_pair(x,y));
			x--,y++;
			while(x<0) x+=n;while(y>=n) y-=n;
		}
		solve(q,clc(q));
	}

	ans=rd;
	for(int i=0;i<n;i++) if(!vis[i])
	{
		top=0;
		dfs(i);
		tk=ans,ls+=top;
		for(int i=2;i<=top;i++) swap(tk[stk[i]],tk[stk[i-1]]);
		if(query(tk)==ls) ans=tk;
		else for(int i=top;i>1;i--) swap(ans[stk[i]],ans[stk[i-1]]);
	}
	check(ans);
}