#include "art.h" #include <bits/stdc++.h> using namespace std; int n; vector<int> nxt[200001]; pair<int,int> cnt[200001]; map<vector<int>, int> mp,in; int publish_(vector<int> v) { if(!in[v])mp[v]=publish(v); in[v]=1; return mp[v]; } void solve(int N) { vector<int> v={1}; n=N; for(int i=2;i<=n;i++) { vector<int> v1=v,v2={i}; v1.push_back(i); for(int j=0;j<v.size();j++) v2.push_back(v[j]); for(int j=i+1;j<=n;j++) { v1.push_back(j); v2.push_back(j); } int p1=publish_(v1); int p2=publish_(v2); int b=(i-1-p1+p2)/2; int a=i-1-b; vector<int> nw; for(int j=0;j<b;j++) nw.push_back(v[j]); nw.push_back(i); for(int j=0;j<a;j++) nw.push_back(v[j+b]); v=nw; for(int j=i+1;j<=n;j++) nw.push_back(j); in[nw]=1; mp[nw]=mp[v2]-b; } answer(v); }