#include <bits/stdc++.h>
#include "art.h"
#define pb push_back
using namespace std;
int inv;
vector<int>order;
vector<int> Solve(int l,int r) {
if(l == r) return {l};
int mid = l + r >> 1;
vector<int>L = Solve(l,mid);
vector<int>R = Solve(mid + 1,r);
int ptr1 = 0,ptr2 = 0,n1 = L.size(),n2 = R.size();
vector<int>v;
while(ptr1 < n1 || ptr2 < n2) {
if(ptr1 == n1) {
v.pb(R[ptr2++]);
}else if(ptr2 == n2) {
v.pb(L[ptr1++]);
}else {
assert(L[ptr1] - 1 >= 0 && L[ptr1] - 1 <= r);
assert(R[ptr2] - 1 >= 0 && R[ptr2] - 1 <= r);
swap(order[L[ptr1] - 1],order[R[ptr2] - 1]);
int inv2 = publish(order);
swap(order[L[ptr1] - 1],order[R[ptr2] - 1]);
if(inv2 < inv) v.pb(R[ptr2++]);
else v.pb(L[ptr1++]);
}
}
return v;
}
void solve(int N) {
for(int i = 1; i <= N; i++) order.pb(i);
inv = publish(order);
answer(Solve(1,N));
}
