#include "art.h"
#include <bits/stdc++.h>
using namespace std;
//void MergeSort(vector<int> v, int left, int right){
// if(left>=right)
// return;
// int mid = left+(right-left)/2;
// MergeSort(v, left, mid);
// MergeSort(v, mid+1, right);
// merge_part(v, left, mid, right);
//}
//void merge_part(vector<int>v, int left, int mid, int right){
// int n1 = mid-left+1;
// int n2 = right-mid;
//
//}
void solve(int n) {
vector <int> vals(n);
for(int i = 0; i < n; i++){
vals[i] = i+1;
}
int k1 = publish(vals);
for(int i = 1; i < n; i++){
vector <int> valstemp = vals;
for(int j = i-1; j >= 0 ; j--){
swap(valstemp[j], valstemp[j + 1]);
}
int k2 = publish(valstemp);
int b = (k2-k1+i)/2;
int a = i-b;
int newpos = b;
for(int j = 1;j <= b;j++)
swap(valstemp[j - 1], valstemp[j]);
swap(vals, valstemp);
k1 = k1-a;
}
answer(vals);
// if(1==1){
// int k = publish(vals);
// cout << k << endl;
// vals = {2,1,3,4,5};
// k = publish(vals);
// cout << k << endl;
// vals = {2,3,1,4,5};
// k = publish(vals);
// cout << k << endl;
// vals = {2,3,4,1,5};
// k = publish(vals);
// cout << k << endl;
// vals = {2,3,4,5,1};
// k = publish(vals);
// cout << k << endl;
// return;
// }
// if(n <= 6){
// do {
// int k = publish(vals);
// if(k==0){
// answer(vals);
// return;
// }
// } while (next_permutation(vals.begin(), vals.end()));
//
// assert(0);
// }
// if(n<=40){
// for(int i = 0; i < n-1; i++){
// for(int j = 0; j < n-1; j++){
// int kfirst = publish(vals);
// swap(vals[j],vals[j+1]);
// int ksecond = publish(vals);
// if(kfirst < ksecond){
// swap(vals[j],vals[j+1]);
// }
// }
// }
// answer(vals);
// return;
// }
// int p = 0;
// int k1 = publish(vals);
//
// valstemp[n-1] = vals[0];
// for(int i = 0; i < n-1; i++){
// valstemp[i] = vals[i+1];
// }
// int k2 = publish(valstemp);
// int b = (k2-k1+p-1)/2;
// int a = p-1-b;
// int newpos = b+1;
//
// for(int i = newpos+1; i < newpos+a; i++){
// valstemp[i] = valstemp[i-1];
// }
// valstemp[newpos] = vals[p];
// publish(valstemp);
// cout << k1 << ' ' << k2 << ' ' << p << endl;
}
