#include <iostream>
#include <vector>
#include <algorithm>
int publish(std::vector<int> R);
void answer(std::vector<int> R);
template <class A, class B, class C>
void mergesort(A begin, A end, B scratch, C comp) {
size_t n = std::distance(begin, end);
if (n <= 1) {
return;
}
auto middle = begin + n/2;
mergesort(begin, middle, scratch, comp);
mergesort(middle, end, scratch, comp);
auto scratch_end = std::merge(begin, middle, middle, end, scratch, comp);
std::copy(scratch, scratch_end, begin);
}
void solve(int N) {
// Used for comparisons
std::vector<int> R;
std::vector<int> ans;
for (int i = 1; i <= N; i++) {
R.push_back(i);
ans.push_back(i);
}
auto comp = [&](int a, int b) {
// std::cerr << "Comparing " << a << " and " << b << '\n';
std::vector<int> local_r = R;
std::swap(local_r[0], local_r[a - 1]);
if (b == 1) {
std::swap(local_r[1], local_r[a - 1]);
} else {
std::swap(local_r[1], local_r[b - 1]);
}
int res1 = publish(local_r);
std::swap(local_r[0], local_r[1]);
int res2 = publish(std::move(local_r));
return res1 < res2;
};
std::vector<int> scratch(R.size());
mergesort(ans.begin(), ans.end(), scratch.begin(), comp);
answer(ans);
}
