#include "xylophone.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
const int N = 5005;
int Paiu[N][N];
void solve(int n) {
vector<int> dif(n, 0);
for(int i = 0; i + 1 < n; ++i) {
Paiu[i][i + 1] = query(i + 1, i + 2);
if(i + 2 < n) Paiu[i][i + 2] = query(i + 1, i + 3);
}
vector<int> type(n, 1);
for(int i = 0; i + 2 < n; ++i) {
if(Paiu[i][i + 1] + Paiu[i + 1][i + 2] != Paiu[i][i + 2]) {
type[i + 2] = -type[i + 1];
} else {
type[i + 2] = type[i + 1];
}
}
{
vector<int> a(n, 0);
for(int i = 1; i < n; ++i) {
if(type[i] == 1) a[i] = a[i - 1] + Paiu[i - 1][i];
else a[i] = a[i - 1] - Paiu[i - 1][i];
}
int mn = *min_element(all(a));
forn(i, n) a[i] += 1 - mn;
set<int> st;
forn(i, n) st.insert(i + 1);
forn(i, n) st.erase(a[i]);
if(!sz(st)) {
map<int, int> pos;
forn(i, n) pos[a[i]] = i;
if(pos[1] < pos[n]) {
for(int i = 0; i < n; ++i) {
answer(i + 1, a[i]);
}
return;
}
}
}
forn(i, n) type[i] = -type[i];
{
vector<int> a(n, 0);
for(int i = 1; i < n; ++i) {
if(type[i] == 1) a[i] = a[i - 1] + Paiu[i - 1][i];
else a[i] = a[i - 1] - Paiu[i - 1][i];
}
int mn = *min_element(all(a));
forn(i, n) a[i] += 1 - mn;
set<int> st;
forn(i, n) st.insert(i + 1);
forn(i, n) st.erase(a[i]);
if(!sz(st)) {
map<int, int> pos;
forn(i, n) pos[a[i]] = i;
if(pos[1] < pos[n]) {
for(int i = 0; i < n; ++i) {
answer(i + 1, a[i]);
}
return;
}
}
}
}
