#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],arr[5001];
//void init(int n){
// for(int i=1;i<=n;i++) cin>>arr[i];
//}
//int query(int a, int b){
// int mx = 0, mn = 1e9;
// for(int i=a;i<=b;i++) mx = max(mx,arr[i]), mn =min(mn,arr[i]);
// return mx-mn;
//}
void solve(int N) {
int n = N;
if(n == 2){
answer(1, 1);
answer(2, 2);
return;
}
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;
int L = 2, R = n-2,M;
bool ada = false;
while(L <= R){
M = (L+R)/2;
x = query(M,n);
if(x == n-1) L = M+1;
else{
ada = true;
now = M-1;
R = M-1;
}
}
//cout<<now<<endl;
if(!ada){
if(query(n-1,n) == n-1) now = n-1;
else now = 1;
}
ans[now] = 1;
int one = now;
// traverse right
if(now == n-1){
ans[n] = n;
vis[n] = true;
}
else{
id = now+1;
x = query(now, id);
ans[id] = x+1;
vis[ans[id]] = true;
while(true){
if(id == n) break;
x = query(id, id+1);
// might be ans[id]+x or ans[id]-x
// so we check bos
// cout<<id<<" "<<id+1<<" "<<x<<" :"<<endl;
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
//cout<<"CEK\n";
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;
vis[ans[id]] = true;
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]);
// for(i=1;i<=n;i++) cout<<ans[i]<<" ";
// cout<<endl;
}
//int main()
//{
// int n;
// cin>>n;
// init(n);
// solve(n);
//
// return 0;
//}
