#include "art.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; void solve(int N) { vector<int> p(N); for(int i=1; i<=N; ++i) p[i-1] = i; int ans = publish(p); int X = 0; vector<int> R = {1}; vector<int> poz(N+1); for(int i=2; i<=N; ++i) { swap(p[0], p[i-1]); int nans = publish(p); int diff = ans-nans; ans = nans; int K = i-2; int Y = diff+1 + 2*K - 2*X; Y/=2; vector<int> stos; for(int j=0; j<Y; ++j) { stos.push_back(R.back()); R.pop_back(); } R.push_back(p[0]); while(stos.size()) { R.push_back(stos.back()); stos.pop_back(); } for(int j=0; j<R.size(); ++j) poz[R[j]] = j; X=0; for(int j=1; j<i; ++j) if(poz[p[j]] < poz[p[0]]) X++; } answer(R); }