#include "xylophone.h"
#include <bits/stdc++.h>
static int A[5000];
void solve(int N) {
int l = 1, r = N;
while(true) {
int m = (l + r) / 2;
// std::cout << l << ' ' << r << '\n';
if(query(l, m) == N-1){
r = m;
}
else if(query(m+1, r) == N-1){
l = m+1;
}
else{
break;
}
}
int li = (l+r) / 2;
int ri = r;
while(li != ri){
int m = (li + ri) / 2;
if(query(l, m) == N-1){
ri = m;
}
else{
li = m+1;
}
}
int Max = li;
std::vector<int> B(N);
B[Max-1] = N-1;
int temp_max = Max-1;
bool accending = false;
for(int i = Max; i < N; i++){
B[i] = B[temp_max] + ((accending? 1: -1) * query(temp_max+1, i+1));
if(B[i] == B[i-1]){
temp_max = i-1;
accending = !accending;
B[i] = B[temp_max] + ((accending? 1: -1) * query(temp_max+1, i+1));
}
}
temp_max = Max-1;
accending = false;
for(int i = Max-2; i >= 0; i--){
B[i] = B[temp_max] + ((accending? 1: -1) * query(i+1, temp_max+1));
if(B[i] == B[i+1]){
temp_max = i+1;
accending = !accending;
B[i] = B[temp_max] + ((accending? 1: -1) * query(i+1, temp_max+1));
}
}
for(int i = 0; i < N; i++){
// std::cout << B[i]+1 << ' ';
answer(i+1, B[i]+1);
}
}
