#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
#define ll long long
#define F first
#define S second
const ll mod = 1e9 + 7;
const ll mxN = 1e5 + 2;
using namespace std;
// void __attribute__((noreturn)) __attribute__((format(printf, 1, 2))) result(const char *msg, ...) {
// va_list args;
// va_start(args, msg);
// vfprintf(stdout, msg, args);
// fprintf(stdout, "\n");
// va_end(args);
// exit(0);
// }
//
// namespace {
// int N;
// int Q = 0;
// const int MAX_Q = 4000;
// const int MAX_N = 4000;
// vector<int> solution;
// } // namespace
//
//
// void __attribute__((noreturn)) answer(vector<int> R) {
// printf("answer({");
// for(int i = 0; i < int(R.size()); ++i) {
// if(i == 0)
// printf("%d", R[i]);
// else
// printf(", %d", R[i]);
// }
// printf("})\n");
// fflush(stdout);
//
//
// if(R == solution)
// result("Correct: %d published ranking(s).", Q);
// else
// result("Wrong answer!");
// }
int publish(vector<int> R);
// printf("publish({");
// for(int i = 0; i < int(R.size()); ++i) {
// if(i == 0)
// printf("%d", R[i]);
// else
// printf(", %d", R[i]);
// }
// printf("})\n");
// fflush(stdout);
//
// if (++Q > MAX_Q)
// result("Too many published rankings!");
//
// if (int(R.size()) != N)
// result("Invalid published ranking!");
//
// set<int> chosen;
// for(auto &x : R) {
// if(x < 1 || x > N || chosen.count(x))
// result("Invalid published ranking!");
// chosen.insert(x);
// }
// vector<int> positions(N+1);
// for(int i = 0; i < N; ++i)
// positions[R[i]] = i;
//
// int complaints = 0;
// for(int i = 0; i < N; ++i) {
// for(int j = i+1; j < N; ++j) {
// if(positions[solution[i]] > positions[solution[j]])
// ++complaints;
// }
// }
//
// return complaints;
// }
void answer(std::vector<int>);
int comp[4002][4002];
bool compare(int a,int b,int N){
if(comp[a][b] != -1) return comp[a][b];
vector<int> ch1,ch2;
ch2.push_back(b);
ch2.push_back(a);
ch1.push_back(a);
ch1.push_back(b);
for(int i = 1;i <= N;i++){
if(i != a && i != b){
ch1.push_back(i);
ch2.push_back(i);
}
}
return comp[a][b] = (publish(ch1) < publish(ch2));
}
vector<int>og;
vector<int>mergeSort(int l,int r,int N){
if(l == r) return og;
int md = (l + r) / 2;
vector<int> a = mergeSort(l,md,N);
vector<int> b = mergeSort(md + 1,r,N);
vector<int> c;
for(int i = 0;i < l;i++){
c.push_back(i + 1);
}
int j = md + 1;
int i = l;
while(i <= md || j <= r){
if(j > r){
c.push_back(a[i]);
i++;
}
else if(i > md){
c.push_back(b[j]);
j++;
}
else if(compare(a[i],b[j],N)){
c.push_back(a[i]);
i++;
}else{
c.push_back(b[j]);
j++;
}
}
for(int i = r;i < N - 1;i++){
c.push_back(i + 1);
}
// cout<<l<<' '<<r<<'\n';
// for(auto x : c) cout<<x<<' ';
// cout<<'\n';
return c;
}
void solve(int N) {
memset(comp,-1,sizeof comp);
for(int i = 1;i <= N;i++) og.push_back(i);
answer(mergeSort(0,N - 1,N));
}
//
// int main() {
// if (scanf("%d", &N) != 1 || N < 2 || N > MAX_N)
// result("Invalid input!");
//
// solution.resize(N);
// set<int> chosen;
// for(auto &x : solution) {
// if(scanf("%d", &x) != 1 || x < 1 || x > N || chosen.count(x))
// result("Invalid input!");
// chosen.insert(x);
// }
//
// solve(N);
//
// result("No answer!");
// }
