#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_set>
#include<unordered_map>
using namespace std;
//void solve(int N);
//int query(int s, int t);
//void answer(int i, int a);
#include "xylophone.h"
map<pair<int, int>, int> mp;
int ask(int a, int b){
if (mp.count(make_pair(a, b))){
return mp[make_pair(a, b)];
}
mp[make_pair(a, b)] = query(a, b);
return mp[make_pair(a, b)];
}
int ans[5002];
set<int> usesd;
void solve(int N) {
int mint = 1;
int maxt = N;
while (mint + 1 < maxt){
int mid = (mint + maxt) >> 1;
if (ask(1, mid) >= N-1){
maxt = mid;
}
else{
mint = mid + 1;
}
}
if (ask(1, mint) >= N-1){
maxt=mint;
}
else{
mint = maxt;
}
int pos = mint;
ans[pos] = N;
for (int i = pos + 1; i <= N; i++){
int dif = ask(i - 1, i);
int n1 = ans[i-1] - dif;
int n2 = ans[i - 1] + dif;
if (n1<1||usesd.count(n1)){
usesd.insert(n2);
ans[i] = n2;
continue;
}
if (n2 > N || usesd.count(n2)){
usesd.insert(n1);
ans[i] = n1;
continue;
}
int F = ask(i-2, i);
int mint = min(min(ans[i - 1], n1), ans[i - 2]);
int maxt = max(max(ans[i - 1], n1), ans[i - 2]);
if (maxt - mint == F){
usesd.insert(n1);
ans[i] = n1;
continue;
}
usesd.insert(n2);
ans[i] = n2;
}for (int i = pos - 1; i >=1 ; i--){
int dif = ask(i, i+1);
int n1 = ans[i + 1] - dif;
int n2 = ans[i + 1] + dif;
if (n1<1 || usesd.count(n1)){
usesd.insert(n2);
ans[i] = n2;
continue;
}
if (n2 > N || usesd.count(n2)){
usesd.insert(n1);
ans[i] = n1;
continue;
}
int F = ask(i, i+2);
int mint = min(min(ans[i + 1], n1), ans[i + 2]);
int maxt = max(max(ans[i + 1], n1), ans[i + 2]);
if (maxt - mint == F){
usesd.insert(n1);
ans[i] = n1;
continue;
}
usesd.insert(n2);
ans[i] = n2;
}
for (int i = 1; i <= N; i++) {
answer(i, ans[i]);
}
}
