#include "xylophone.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
using namespace std;
bool vis[10001];
int ans[5001];
void solve(int N) {
int n = N;
if(n == 2){
answer(1, 1);
answer(2, 2);
}
int i,j,t;
vis[1] = vis[0] = true;
for(i=n+1;i<=2*n;i++) vis[i] = true;
int now = 1,id = 2,x;
while(true){
if(id == n-1){
now = id;
break;
}
x = query(id, n);
if(x == n-1) now = id,id++;
else break;
}
ans[now] = 1;
int one = now;
// traverse right
if(now == n-1) ans[n] = n;
else{
id = now+1;
x = query(now, id);
ans[id] = x+1;
while(true){
if(id == n) break;
x = query(id, id+1);
// might be ans[id]+x or ans[id]-x
// so we check bos
if(ans[id]-x <= 1){
ans[id+1] = ans[id]+x;
vis[ans[id+1]] = true;
id++;
continue;
}
if(vis[ans[id]-x]){
ans[id+1] = ans[id]+x;
vis[ans[id+1]] = true;
id++;
continue;
}
if(vis[ans[id]+x]){
ans[id+1] = ans[id]-x;
vis[ans[id+1]] = true;
id++;
continue;
}
if(ans[id]+x == n){
ans[id+1] = n;
vis[ans[id+1]] = true;
id++;
continue;
}
// kita gatau ini + atau - jadi kita cek
int bil = x;
x = query(id-1, id+1);
if(ans[id-1] < ans[id]){
// min max
if(x == ans[id] - ans[id-1]){
// berarti middle
ans[id+1] = ans[id]-bil;
vis[ans[id+1]] = true;
id++;
continue;
}
if(x == bil){
ans[id+1] = ans[id]-bil;
vis[ans[id+1]] = true;
id++;
continue;
}
ans[id+1] = ans[id]+bil;
vis[ans[id+1]] = true;
id++;
}
else{
if(x == ans[id-1] - ans[id]){
ans[id+1] = ans[id]+bil;
vis[ans[id+1]] = true;
id++;
continue;
}
if(x == bil){
ans[id+1] = ans[id]+bil;
vis[ans[id+1]] = true;
id++;
continue;
}
ans[id+1] = ans[id]-bil;
vis[ans[id+1]] = true;
id++;
}
}
}
if(now > 1){
id = now-1;
x = query(id, now);
ans[id] = x+1;
while(true){
if(id == 1) break;
x = query(id-1, id);
if(ans[id]-x <= 1){
ans[id-1] = ans[id]+x;
vis[ans[id-1]] = true;
id--;
continue;
}
if(vis[ans[id]-x]){
ans[id-1] = ans[id]+x;
vis[ans[id-1]] = true;
id--;
continue;
}
if(vis[ans[id]+x]){
ans[id-1] = ans[id]-x;
vis[ans[id-1]] = true;
id--;
continue;
}
// kita gatau
int bil = x;
x = query(id-1, id+1);
if(ans[id+1] > ans[id]){
// min max
if(x == ans[id+1]-ans[id]){
ans[id-1] = ans[id]+bil;
vis[ans[id-1]] = true;
id--;
continue;
}
if(x > bil){
ans[id-1] = ans[id]-bil;
vis[ans[id-1]] = true;
id--;
continue;
}
ans[id-1] = ans[id]+bil;
vis[ans[id-1]] = true;
id--;
}
else{
// max min
if(x == ans[id]-ans[id+1]){
ans[id-1] = ans[id]-bil;
vis[ans[id-1]] = true;
id--;
continue;
}
if(bil == x){
ans[id-1] = ans[id]-bil;
vis[ans[id-1]] = true;
id--;
continue;
}
ans[id-1] = ans[id]+bil;
vis[ans[id-1]] = true;
id--;
}
}
}
for(i=1;i<=n;i++) answer(i, ans[i]);
}
//int main()
//{
// solve(5);
//
// return 0;
//}
