#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i += (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
typedef long long ll;
static int A[5000];
void solve(int N) {
vector<array<int, 2>> nx(N + 1);
FOR(i, 1, N + 1, 1){
FOR(j, 1, 3, 1){
if(i + j < N + 1){
nx[i][j - 1] = query(i, i + j);
}
}
}
auto construct = [&](int f, int s){ // if I know prev 2, determines next; brute first. brute second as first + diff or first - diff; validate seq later
vector<int> res(N + 1);
res[1] = f;
res[2] = s;
FOR(i, 3, N + 1, 1){
if(res[i - 2] > res[i - 1]){
if(nx[i - 2][0] + nx[i - 1][0] == nx[i - 2][1]){
res[i] = res[i - 1] - nx[i - 1][0];
}
else{
res[i] = res[i - 1] + nx[i - 1][0];
}
}
else{
if(nx[i - 2][0] + nx[i - 1][0] == nx[i - 2][1]){
res[i] = res[i - 1] + nx[i - 1][0];
}
else{
res[i] = res[i - 1] - nx[i - 1][0];
}
}
}
return res;
};
auto validate = [&](vector<int> &res){
FOR(i, 1, N + 1, 1){
if(res[i] > N || res[i] < 1)
return false;
}
vector<bool> used(N + 1, false);
FOR(i, 1, N + 1, 1){
used[res[i]] = true;
}
FOR(i, 1, N + 1, 1){
if(used[i] == false)
return false;
}
int f = 0;
int s = 0;
FOR(i, 1, N + 1, 1){
if(res[i] == 1)
f = i;
if(res[i] == N)
s = i;
}
if(f > s)
return false;
return true;
};
vector<int> res;
FOR(i, 1, N + 1, 1){
res = construct(i, i + nx[1][0]);
if(validate(res))
break;
res = construct(i, i - nx[1][0]);
if(validate(res))
break;
}
FOR(i, 1, N + 1, 1){
answer(i, res[i]);
}
}
