#include "art.h"
#include <bits/stdc++.h>
using namespace std;
//
// --- Sample implementation for the task art ---
//
// To compile this program with the sample grader, place:
// art.h art_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
// g++ -std=c++17 art_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//
random_device rd;
mt19937 g(rd());
void solve(int n) {
vector <int> a(n);
iota(a.begin(), a.end(), 1);
shuffle(a.begin(), a.end(), g);
int lst = publish(a);
map <vector <int>, int> mp; mp[a] = lst;
for (int i = n - 2; i >= 0; i --) {
int l = i, r = n - 2; int k = i;
bool ok = false;
while (l <= r) {
int m = (l + r) / 2;
vector <int> b = a;
int x = i;
while (x < m) {
swap(b[x], b[x + 1]); x ++;
}
int ans1 = (mp.find(b) != mp.end() ? mp[b] : mp[b] = publish(b));
swap(b[m], b[m + 1]);
int ans2 = (mp.find(b) != mp.end() ? mp[b] : mp[b] = publish(b));
if (ans2 == 0) { k = m + 1; ok = true; break;}
if (ans1 > ans2) k = m + 1, l = m + 1;
else r = m - 1;
}
int x = i;
while (x < k) swap(a[x], a[x + 1]), x ++;
if (ok) break;
}
answer(a);
// publish(order);
// answer(order);
}
