#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,i+2);
int z=abs(a[i+1]-a[i+2]);
if (y>z){
if (a[i+1]>a[i+2]){
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);
}
}
else{
if (a[i+1]>a[i+2]){
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(i-2,i);
int z=abs(a[i-1]-a[i-2]);
if (y>z){
if (a[i-1]>a[i-2]){
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);
}
}
else{
if (a[i-1]>a[i-2]){
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(i-2,i);
int z=abs(a[i-1]-a[i-2]);
if (y>z){
if (a[i-1]>a[i-2]){
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);
}
}
else{
if (a[i-1]>a[i-2]){
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;
}
