#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
#define ll long long
#define all(x) (x).begin(), (x).end()
#define endl '\n'
static int A[5001];
static int diff_[5001];
set<int> used;
bool brute_left (int i, int last, int n,set<int>cur, bool st) {
if (last<1||last>n) return 0;
if ((used.count(last)&&!st)||cur.count(last))return 0;
if (i==0)return 1;
int down = last - diff_[i+1];
cur.insert(last);
if (brute_left(i-1,down,n,cur,0)){
A[i]=down;
return 1;
}
int up=last+diff_[i+1];
if (brute_left(i-1,up,n,cur,0)){
A[i]=up;
return 1;
}
return 0;
}
bool brute_right(int i, int last, int n, set<int> cur,bool st){
if (last<1||last>n)return 0;
if((used.count(last)&&!st)||cur.count(last))return 0;
if (i==n+1)return 1;
cur.insert(last);
int down = last - diff_[i];
if(brute_right(i+1,down,n,cur,0)){
A[i]=down;return 1;
}
int up=last+diff_[i];
if(brute_right(i+1,up,n,cur,0)){
A[i]=up;return 1;
}
return 0;
};
void solve(int N) {
for (int i = 1; i <= N; i++)
A[i] = -1;
int lo = 1;
int hi = N;
int idx = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (query(mid, N) == N - 1) {
idx = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
A[idx] = 1;
int done = 1;
if (idx > 1){
++done;
A[idx - 1] = query(idx - 1, idx) + 1;
}
if (idx < N){
++done;
A[idx + 1] = query(idx, idx + 1) + 1;
}
for (int j = idx - 2; j >= 1; j--) {
if (N - done <= 20) break;
int q1 = query(j, j + 2);
int q2 = query(j, j + 1);
diff_[j+1]=q2;
int diff = abs(A[j + 1] - A[j + 2]);
if (diff == q1) {
if (A[j + 1] > A[j + 2])
A[j] = A[j + 1] - q2;
else
A[j] = A[j + 1] + q2;
} else if (q2 == q1) {
if (A[j + 1] > A[j + 2])
A[j] = A[j + 1] - q2;
else
A[j] = A[j + 1] + q2;
} else {
if (A[j + 1] > A[j + 2])
A[j] = A[j + 1] + q2;
else
A[j] = A[j + 1] - q2;
}
++done;
}
for (int j = idx + 2; j <= N; j++) {
if (N - done <= 20) break;
int q1 = query(j - 2, j);
int q2 = query(j - 1, j);
diff_[j]=q2;
int diff = abs(A[j - 1] - A[j - 2]);
if (diff == q1) {
if (A[j - 1] > A[j - 2])
A[j] = A[j - 1] - q2;
else
A[j] = A[j - 1] + q2;
} else if (q2 == q1) {
if (A[j - 1] > A[j - 2])
A[j] = A[j - 1] - q2;
else
A[j] = A[j - 1] + q2;
} else {
if (A[j - 1] > A[j - 2])
A[j] = A[j - 1] + q2;
else
A[j] = A[j - 1] - q2;
}
++done;
}
int left = 0;
int right = N + 1;
for (int i = 1; i <= N; i++){
if (A[i] != -1) break;
left=i;
}
for (int i = N; i >= 1; i--) {
if (A[i] != -1) break;
right=i;
}
for (int i = left + 1; i >= 2; i--)
diff_[i]=query(i-1,i);
for (int i = right;i<=N;i++)
diff_[i]=query(i-1,i);
for (int i = 1; i <= N; i++)
if (A[i] != -1)
used.insert(A[i]);
brute_left(left,A[left+1],N,{},1);
brute_right(right,A[right-1],N,{},1);
for (int i = 1; i <= N; i++)
answer(i, A[i]);
}
