#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include "xylophone.h"
using namespace std;
static const int N_MAX = 5000;
static const int Q_MAX = 10000;
static int N;
static int A[N_MAX];
static bool used[N_MAX];
static int query_c;
static int answer_c;
void solve(int n){
int l=1;
int h=n;
int m=(l+h)/2;
while (l<h){
int x=query(1,m);
if (x==n-1){
h=m;
}
else{
l=m+1;
}
m=(l+h)/2;
}
int r=m;
l=1;
h=r;
m=(l+h+1)/2;
while (l<h){
int x=query(m,r);
if (x==n-1){
l=m;
}
else{
h=m-1;
}
m=(l+h+1)/2;
}
answer(l,1);
answer(r,n);
vector<int>a(n+1);
a[l]=1;
a[r]=n;
map<pair<int,int>,int>d;
d[{l,l}]=0;
vector<int>vi(n+1);
vi[1]=1;
vi[n]=1;
for (int i=l-1;i>=1;i--){
int x=query(i,i+1);
if (a[i+1]-x<1 or vi[a[i+1]-x]){
a[i]=a[i+1]+x;
vi[a[i+1]+x]=1;
answer(i,a[i+1]+x);
continue;
}
if (a[i+1]+x>n or vi[a[i+1]+x]){
a[i]=a[i+1]-x;
vi[a[i+1]-x]=1;
answer(i,a[i+1]-x);
continue;
}
int y=query(i,l);
if (!d[{i+1,l}]){
d[{i+1,l}]=query(i+1,l);
}
int z=d[{i+1,l}];
if (z>y){
a[i]=a[i+1]+x;
vi[a[i+1]+x]=1;
answer(i,a[i+1]+x);
}
else{
a[i]=a[i+1]-x;
vi[a[i+1]-x]=1;
answer(i,a[i+1]-x);
}
}
for (int i=l+1;i<r;i++){
int x=query(i-1,i);
if (a[i-1]-x<1 or vi[a[i-1]-x]){
a[i]=a[i-1]+x;
vi[a[i-1]+x]=1;
answer(i,a[i-1]+x);
continue;
}
if (a[i-1]+x>n or vi[a[i-1]+x]){
a[i]=a[i-1]-x;
vi[a[i-1]-x]=1;
answer(i,a[i-1]-x);
continue;
}
int y=query(l,i);
if (!d[{i-1,l}]){
d[{i-1,l}]=query(l,i-1);
}
int z=d[{i-1,l}];
if (z>y){
a[i]=a[i-1]+x;
vi[a[i-1]+x]=1;
answer(i,a[i-1]+x);
}
else{
a[i]=a[i-1]-x;
vi[a[i-1]-x]=1;
answer(i,a[i-1]-x);
}
}
for (int i=r+1;i<=n;i++){
int x=query(i-1,i);
if (a[i-1]-x<1 or vi[a[i-1]-x]){
a[i]=a[i-1]+x;
vi[a[i-1]+x]=1;
answer(i,a[i-1]+x);
continue;
}
if (a[i-1]+x>n or vi[a[i-1]+x]){
a[i]=a[i-1]-x;
vi[a[i-1]-x]=1;
answer(i,a[i-1]-x);
continue;
}
int y=query(r,i);
if (!d[{i-1,l}]){
d[{i-1,l}]=query(r,i-1);
}
int z=d[{i-1,l}];
if (z>y){
a[i]=a[i-1]-x;
vi[a[i-1]-x]=1;
answer(i,a[i-1]-x);
}
else{
a[i]=a[i-1]+x;
vi[a[i-1]+x]=1;
answer(i,a[i-1]+x);
}
}
return;
}
