#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
int p[5002],a[5002],mem[5002][5002];
int QQ(int l,int r) {
if(mem[l][r] != -1) {
return mem[l][r];
}
return mem[l][r] = query(l,r);
}
int n_;
bool bad(int x) {
return (x < 1 || x > n_ || p[x]);
}
void make(int v,int val) {
a[v] = val;
p[val] = v;
}
void solve(int n) {
n_ = n;
memset(mem,-1,sizeof(mem));
memset(p,0,sizeof(p));
memset(a,0,sizeof(a));
int nd = n - 1;
int l = 1,r = n;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(QQ(1,mid) == nd) {
r = mid;
} else {
l = mid;
}
}
p[n] = r;
l = 1,r = p[n];
while(r - l > 1) {
int mid = (l + r) >> 1;
if(QQ(mid,p[n]) == nd) {
l = mid;
} else {
r = mid;
}
}
p[1] = l;
a[p[1]] = 1;
a[p[n]] = n;
int mx = 1;
if(p[1] - 1 >= 1) {
make(p[1] - 1,1 + QQ(p[1] - 1,p[1]));
}
for(int i = p[1] - 2;i >= 1;i--) {
int t2, t1, val;
int t = QQ(i,i + 1);
if(bad(a[i + 1] + t)) {
val = a[i + 1] - t;
} else if(bad(a[i + 1] - t)) {
val = a[i + 1] + t;
}
else {
t2 = QQ(i,i + 2);
if(a[i + 2] > a[i + 1]) {
if(t2 == a[i + 2] - (a[i + 1] - t)) {
val = a[i + 1] - t;
} else {
val = a[i + 1] + t;
}
} else {
if(t2 == a[i + 1] + t - a[i + 2]) {
val = a[i + 1] + t;
} else {
val = a[i + 1] - t;
}
}
}
// cout << i << ' ' << val << ' ' << (a[i + 2] > a[i + 1]) << '\n';
p[val] = i;
a[i] = val;
}
mx = 1;
if(p[1] + 1 < p[n]) {
make(p[1] + 1,1 + QQ(p[1],p[1]+1));
}
for(int i = p[1] + 2;i < p[n];i++) {
int val;
int t2, t1;
int t = QQ(i - 1,i);
if(bad(a[i - 1] + t)) {
val = a[i - 1] - t;
} else if(bad(a[i - 1] - t)) {
val = a[i - 1] + t;
} else{
t2 = QQ(i - 2,i);
if(a[i - 2] > a[i - 1]) {
if(t2 == a[i - 2] - (a[i - 1] - t)) {
val = a[i - 1] - t;
} else {
val = a[i - 1] + t;
}
} else {
if(t2 == a[i - 1] + t - a[i - 2]) {
val = a[i - 1] + t;
} else {
val = a[i - 1] - t;
}
}
}
// cout << i << ' ' << val << '\n';
p[val] = i;
a[i] = val;
}
int mn = n;
for(int i = p[n] + 1;i <= n;i++) {
int val, T = QQ(p[n],i);
if(T != n - mn) {
mn = val = n - T;
} else {
int t2, t1;
int t = QQ(i - 1,i);
if(bad(a[i - 1] + t)) {
val = a[i - 1] - t;
} else if(bad(a[i - 1] - t)) {
val = a[i - 1] + t;
} else{
t2 = QQ(i - 2,i);
if(a[i - 2] > a[i - 1]) {
if(t2 == a[i - 2] - (a[i - 1] - t)) {
val = a[i - 1] - t;
} else {
val = a[i - 1] + t;
}
} else {
if(t2 == a[i - 1] + t - a[i - 2]) {
val = a[i - 1] + t;
} else {
val = a[i - 1] - t;
}
}
}
}
p[val] = i;
a[i] = val;
}
for(int i = 1;i <= n;i++) {
answer(p[i],i);
}
}
