#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int A[5000];
void solve(int n){
vector<int> ans(n+1);
vector<bool> got(n+1, 0);
int low=0, high=n+1;
while (low+1<high){
int mid=(low+high)/2;
if (query(mid, n)==n-1)low=mid;
else high=mid;
}
got[1]=1;
ans[low]=1;
if (low+1<=n)ans[low+1]=1+query(low, low+1), got[ans[low+1]]=1;
for (int i=low+2; i<=n; ++i){
int d=query(i-1, i);
if (ans[i-1]-d<=0||got[ans[i-1]-d])ans[i]=ans[i-1]+d;
else if (ans[i-1]+d>n||got[ans[i-1]+d])ans[i]=ans[i-1]-d;
else{
int temp=query(i-2, i);
if (ans[i-2]>ans[i-1]){
if (temp==ans[i-2]-ans[i-1]+d)ans[i]=ans[i-1]-d;
else ans[i]=ans[i-1]+d;
}
else{
if (temp==ans[i-1]-ans[i-2]+d)ans[i]=ans[i-1]+d;
else ans[i]=ans[i-1]-d;
}
}
got[ans[i]]=1;
}
if (low>1)ans[low-1]=1+query(low-1, low), got[ans[low-1]]=1;
for (int i=low-2; i>=1; --i){
int d=query(i, i+1);
if (ans[i+1]-d<=0||got[ans[i+1]-d])ans[i]=ans[i+1]+d;
else if (ans[i+1]+d>n||got[ans[i+1]+d])ans[i]=ans[i+1]-d;
else{
int temp=query(i, i+2);
if (ans[i+2]>ans[i+1]){
if (temp==ans[i+2]-ans[i+1]+d)ans[i]=ans[i+1]-d;
else ans[i]=ans[i+1]+d;
}
else{
if (temp==ans[i+1]-ans[i+2]+d)ans[i]=ans[i+1]+d;
else ans[i]=ans[i+1]-d;
}
}
got[ans[i]]=1;
}
for (int i=1; i<=n; ++i)answer(i, ans[i]);
}
