#include "monster.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii; 
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
  return x*w;
}

namespace {
  const int maxN=1005;
  int xn,deg[maxN],e[maxN][maxN],qcnt;
}

int qry(int x,int y) {
  if(y>=xn) return 1;
  if(e[x][y]) return e[x][y];
  ++qcnt;
  if(Query(x,y)) e[x][y]=1, e[y][x]=-1;
  else e[x][y]=-1, e[y][x]=1;
  return e[x][y];
}

vi solvesmall(vi p) {
  int n=p.size();
  rep(i,0,xn-1) deg[i]=0;
  rep(i,0,n-1) rep(j,i+1,n-1) qry(p[i],p[j]);
  rep(i,0,n-1) rep(j,0,n-1) deg[p[i]]+=(e[p[i]][p[j]]>0);
  int l=0, r=0;
  rep(i,0,n-1) if(deg[p[i]]==0) l=1;
  rep(i,0,n-1) if(deg[p[i]]==n-1) r=1;
  if(l&&r) return {l,r,0};
  else if(l) return {l};
  else if(r) return {0,r};
  vi q(n);
  rep(i,0,n-1) q[i]=-1;
  rep(i,0,n-1) {
    int u=p[i];
    if(deg[u]==l+1) {
      if(q[l+1]==-1) q[l+1]=u;
      else q[l+0]=u;
    } else if(deg[u]==n-2-r) {
      if(q[n-2-r]==-1) q[n-2-r]=u;
      else q[n-1-r]=u;
    } else q[deg[u]]=u;
  }
  if(qry(q[l],q[l+1])==-1) swap(q[l],q[l+1]);
  if(qry(q[n-2-r],q[n-1-r])==-1) swap(q[n-2-r],q[n-1-r]);
  return q;
}

vi Solve(int n) {
  vi p={0}; xn=n;
  if(n>8) {
    rep(i,1,n-1) {
      int l=0, r=i-1, pos=i;
      while(l<=r) {
        int mid=l+r>>1;
        if(qry(p[mid],i)==1) pos=mid, r=mid-1;
        else l=mid+1;
      }
      p.insert(p.begin()+pos,i);
    }
    p.eb(n);
    int lb=4,rb=n-5;
    vi t={p[0],p[1],p[2],p[3]}; t=solvesmall(t);
    if(t.size()==4) {
      bool flag=1;
      rep(i,0,3) flag&=(p[i]==t[3-i]);
      if(flag) lb=0;
      else rep(i,0,3) p[i]=t[i];
    } else if(t.size()==3) lb=2;
    else if(t.size()==2) lb=3;
    else if(t.size()==1) lb=1;
    t={p[n-4],p[n-3],p[n-2],p[n-1]}; t=solvesmall(t);
    if(t.size()==4) {
      bool flag=1;
      rep(i,0,3) flag&=(p[n-4+i]==t[3-i]);
      if(flag) rb=n-1;
      else rep(i,0,3) p[n-4+i]=t[i];
    } else if(t.size()==3) rb=n-3;
    else if(t.size()==2) rb=n-2;
    else if(t.size()==1) rb=n-4;
    vi tb;
    rep(i,lb,rb) {
      int j=i+2; if(j>rb) break;
      if(i>0&&qry(p[i-1],p[i])==1) continue;
      if(i==lb) {
        if(i>1&&qry(p[i-2],p[i])==1) continue;
        if(i>2&&qry(p[i-3],p[i])==1) continue;
        if(i>3&&qry(p[i-4],p[i])==1) continue;
      }
      while(j<=rb+1&&qry(p[i],p[j])==1) j++;
      if(j!=i+2&&qry(p[i+1],p[j-1])==-1) {
        if(j==i+3&&qry(p[j],p[i])+qry(p[j],p[i+1])+qry(p[j],p[i+2])==3) {
          tb.eb(i); i=j-1; continue;
        }
        --j;
      }
      chmin(j,rb+1);
      reverse(p.begin()+i,p.begin()+j);
      i=j-1;
    }
    if(tb.size()&&tb[0]<=3) {
      int k=max(3,tb[0]+2); t.clear();
      rep(i,0,k) t.eb(p[i]); t=solvesmall(t);
      rep(i,0,k) p[i]=t[i];
    } else {
      t={p[0],p[1],p[2],p[3]}; t=solvesmall(t);
      rep(i,0,3) p[i]=t[i];
    }
    for(int pos:tb) if(pos>3) {
      t={p[pos-1],p[pos],p[pos+1],p[pos+2]}; t=solvesmall(t);
      rep(i,0,3) p[pos-1+i]=t[i];
    }
    t={p[n-6],p[n-5],p[n-4],p[n-3],p[n-2],p[n-1]}; t=solvesmall(t);
    rep(i,0,5) p[n-6+i]=t[i];
  } else {
    rep(i,1,n-1) p.eb(i);
    p=solvesmall(p);
  }
  vi q(n);
  rep(i,0,n-1) q[p[i]]=i;
  return q;
}