#include<bits/stdc++.h>
#include "puzzle.h"
#define LL int
#define SZ(x) ((LL)(x.size()))
#define all(x) (x).begin(),(x).end()
using namespace std;
/*inline LL read(){
  LL q=0,w=1;char ch=getchar();
  while(ch>'9' || ch<'0'){if(ch=='-')w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){q=q*10+(ch-'0');ch=getchar();}
  return q*w;
}
void write(LL x){
  if(x<0){putchar('-');x=(-x);}
  if(x>9)write(x/10);
  putchar('0'+x%10);
}
inline void writeln(LL x){write(x);puts("");}
inline void writecs(LL x){write(x);putchar(' ');}*/

inline void dmin(LL &x,LL y){if(x>y)x=y;return ;}
inline void dmax(LL &x,LL y){if(x<y)x=y;return ;}

#define cout cerr
#define pb push_back

namespace GenHelper{
#define ull unsigned long long
  ull seed=19260817ull;
  inline void Get(){seed^=(seed<<7);seed^=(seed>>11);seed^=(seed<<13);}
  inline ull Rand(){Get();return (seed^(seed<<32ull));}
}using GenHelper::Rand;
inline LL random(LL l,LL r){return (Rand()%(r-l+1)+l);}

const LL N = 1000+95 ;
LL n;bitset<N>p,q;LL ans[N],X=-1,Y=-1,TEMP;
//(X,Y) 表示一组已经找到的匹配

inline void link(LL x,LL y){//当前确定了 p[x]=y
  p[x]=0;q[y]=0;ans[x]=y;
  if(X==-1){X=x;Y=y;}
  TEMP++;return ;
}

vector<LL>__GET(vector<LL>&a,vector<LL>&b){
  vector<LL>p(n);
  for(LL i=0;i<n;i++)p[i]=ans[i];
  for(LL i=0;i<SZ(a);i++)p[a[i]]=b[i];
  for(LL i=0;i<n;i++)assert(p[i]!=-1);
  return p;
}

inline LL GET(vector<LL>&a,vector<LL>&b){
  vector<LL>p=__GET(a,b);
  return query(p);
}

inline bool __brute(LL x,LL y){//极其暴力的判断单点的 p[x] 是否等于 y ,错误率 0.0101 .
  for(LL TC=1;TC<=20;TC++){
    vector<LL>p(n);for(LL i=0;i<n;i++)p[i]=i;
    for(LL i=0;i<n;i++)swap(p[i],p[random(0,(n-1))]);
    for(LL i=0;i<n;i++)if(p[i]==y){swap(p[x],p[i]);break;}
    if(query(p)==0)return 0;
  }
  return 1;
}
inline bool brute(LL x,LL y){//判断单点 p[x] 是否等于 y
  if(X==-1)return __brute(x,y);
  //用一组正确的匹配强行拆解掉原有匹配
  vector<LL>p(n);for(LL i=0;i<n;i++)p[i]=i;
  for(LL i=0;i<n;i++)swap(p[i],p[random(0,(n-1))]);
  for(LL i=0;i<n;i++)if(p[i]==Y){swap(p[X],p[i]);break;}
  for(LL i=0;i<n;i++)if(p[i]==y){swap(p[x],p[i]);break;}
  LL k=query(p);swap(p[x],p[X]);LL _k=query(p);
  return ((k==_k+2)?(1):(0));
}

void solve(vector<LL>a,vector<LL>b,LL l,LL r,LL k){
  if(l==r){link(a[l],b[l]);return ;}
  LL mid=(l+r)>>1;
  if(l==mid){
    assert((r-l+1)==2);
    vector<LL>c=b;swap(c[l],c[r]);
    LL _k=GET(a,c);if(k==_k)return ;//如果相等只有一种可能,那就是这两个元素都不是正确的匹配
    if(k<_k){swap(b,c);swap(k,_k);}//此时(b,k)必然存在至少一组合法正确匹配
    if(k==_k+2){link(a[l],b[l]);link(a[r],b[r]);return ;}//此时找到了两组正确的匹配

    if(brute(a[l],b[l])){link(a[l],b[l]);}
    else {link(a[r],b[r]);}
    return ;
  }
  if((r-l+1)<=4){//(mid-l+1)<=2
    vector<LL>vc_a={l,l+1},vc_b={l,l+1};
    if(random(0,1))swap(vc_a[0],vc_a[1]);
    if(random(0,1))swap(vc_b[0],vc_b[1]);
    for(auto x:vc_a)
      for(auto y:vc_b)if(brute(a[x],b[y])){link(a[x],b[y]);return ;}
    solve(a,b,mid+1,r,k);return ;
  }
  for(LL TC=1;TC<=6;TC++){
    vector<LL>c=b;
    while(true){
      for(LL i=l;i<=mid;i++)swap(c[i],c[random(l,mid)]);
      LL fl=0;for(LL i=l;i<=mid;i++)if(b[i]!=c[i]){fl=1;break;}
      if(fl)break;
    }
    LL _k=GET(a,c);
    if(k>_k){solve(a,b,l,mid,k);return ;}
    if(k<_k){solve(a,c,l,mid,_k);return ;}
  }
  solve(a,b,mid+1,r,k);
  return ;
}

void play(LL _n_){
  n=_n_;for(LL t=0;t<n;t++){p[t]=q[t]=1;ans[t]=-1;}
  
  while(true){
    vector<LL>a,b;
    for(LL t=0;t<n;t++){
      if(p[t])a.pb(t);
      if(q[t])b.pb(t);
    }
    assert(SZ(a)==SZ(b));if(!SZ(a))break;
    LL len=SZ(a)-1;if(!len){ans[a[0]]=b[0];break;}
    for(LL t=0;t<=len;t++)swap(b[t],b[random(0,len)]);


    LL k=GET(a,b);
    if(k>TEMP)solve(a,b,0,len,k);
  }
  vector<LL>p(n);
  for(LL i=0;i<n;i++){p[i]=ans[i];assert(ans[i]!=-1);}
  check(p);return ;
}
/*
my test data:
4
2 3 0 1 

*/