/*
ID: hedichehaidar
TASK: photo
LANG: C++11
*/
#include<bits/stdc++.h>
#include "xylophone.h"
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vdd vector<pdd>
#define dte tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = INF + 7;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;
int n;
vi v;
/*int query(int i , int j){
if(i > j || i < 1 || j > n) cout << "wrong3" << endl;
// cout << i << " " << j << endl;
int mn = INF, mx = -1;
for(int x = i - 1 ; x <= j - 1 ; x++){
mn = min(mn , v[x]);
mx = max(mx , v[x]);
}
return mx - mn;
}
int answer(int i , int a){
return 0;
cout << i << " " << a << "\n";
}*/
bool seen[5050];
vi res;
void solve(int N){
n = N;
res.assign(n , 0);
int l = 0 , r = n - 1;
int ans = -1 , d = n - 1;
while(l <= r){
int mid = (l + r) / 2 ;
int q = query(1 , mid);
if(q != d){
l = mid + 1;
}
else{
ans = mid;
r = mid - 1;
}
}
l = 0 ; r = ans;
int ans2 = -1;
while(l <= r){
int mid = (l+ r) / 2;
int q = query(mid , ans);
if(q != d){
r = mid - 1;
}
else{
ans2 = mid;
l = mid + 1;
}
}
swap(ans , ans2);
res[ans - 1] = 1;
res[ans2 - 1] = n;
if(ans != 1) {
res[ans - 2] = query(ans - 1 , ans) + 1;
}
if(ans2 != n){
res[ans2] = res[ans2 - 1] - query(ans2 , ans2 + 1);
}
if(ans != ans2 - 1){
res[ans] = query(ans , ans + 1) + 1;
if(ans != ans2 - 2){
res[ans2 - 2] = res[ans2 - 1] - query(ans2 - 1 , ans2);
}
}
for(auto c : res ) seen[c] = true;
int cur = ans - 3;
while(cur >= 0){
int q1 = query(cur + 1 , cur + 2);
if(res[cur + 1] - q1 < 1 || seen[res[cur + 1] - q1]){
res[cur] = res[cur + 1] + q1;
}
else if(res[cur + 1] + q1 > n || seen[res[cur + 1] + q1]){
res[cur] = res[cur + 1] - q1;
}
else{
int q2 = query(cur + 1 , cur + 3);
if(q1 == q2){
if(res[cur + 1] < res[cur + 2]){
res[cur] = res[cur + 1] + q1;
}
else res[cur] = res[cur + 1] - q1;
}
else if(q2 == abs(res[cur + 1] - res[cur + 2])){
if(res[cur + 1] < res[cur + 2]) res[cur] = res[cur + 1] + q1;
else res[cur] = res[cur + 1] - q1;
}
else if(res[cur + 1] > res[cur + 2]) res[cur] = res[cur + 1] + q1;
else res[cur] = res[cur + 1] - q1;
}
seen[res[cur]] = true;
cur--;
}
cur = ans + 1 ;
while(cur < ans2 - 2){
int q1 = query(cur , cur + 1);
if(res[cur - 1] - q1 < 1 || seen[res[cur - 1] - q1]){
res[cur] = res[cur - 1] + q1;
}
else if(res[cur - 1] + q1 > n || seen[res[cur - 1] + q1]){
res[cur] = res[cur - 1] - q1;
}
else{
int q2 = query(cur - 1 , cur + 1);
if(q1 == q2){
if(res[cur - 1] < res[cur - 2]){
res[cur] = res[cur - 1] + q1;
}
else res[cur] = res[cur - 1] - q1;
}
else if(q2 == abs(res[cur - 1] - res[cur - 2])){
if(res[cur - 1] < res[cur - 2]) res[cur] = res[cur - 1] + q1;
else res[cur] = res[cur - 1] - q1;
}
else if(res[cur - 1] > res[cur - 2]) res[cur] = res[cur - 1] + q1;
else res[cur] = res[cur - 1] - q1;
}
seen[res[cur]] = true;
cur++;
}
cur = ans2 + 1;
while(cur < n){
int q1 = query(cur , cur + 1);
if(res[cur - 1] - q1 < 1 || seen[res[cur - 1] - q1]){
res[cur] = res[cur - 1] + q1;
}
else if(res[cur - 1] + q1 > n || seen[res[cur - 1] + q1]){
res[cur] = res[cur - 1] - q1;
}
else{
int q2 = query(cur - 1 , cur + 1);
if(q1 == q2){
if(res[cur - 1] < res[cur - 2]){
res[cur] = res[cur - 1] + q1;
}
else res[cur] = res[cur - 1] - q1;
}
else if(q2 == abs(res[cur - 1] - res[cur - 2])){
if(res[cur - 1] < res[cur - 2]) res[cur] = res[cur - 1] + q1;
else res[cur] = res[cur - 1] - q1;
}
else if(res[cur - 1] > res[cur - 2]) res[cur] = res[cur - 1] + q1;
else res[cur] = res[cur - 1] - q1;
}
seen[res[cur]] = true;
cur++;
}
for(int i = 0 ; i < n ; i++) answer(i + 1 , res[i]);
}
/*int main(){
//ifstream fin ("race.in");
//ofstream fout ("race.out");
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int N = 5000;
for(int i = 0 ; i < N ; i++){
int x = i + 1;
v.pb(x);
}
random_shuffle(all(v));
// for(auto c : v) cout << c << " "; cout << "\n";
solve(N);
//for(auto c : res) cout << c << " " ; cout << "\n\n";
for(int i = 0 ; i < n ; i++) if(v[i] != res[i]) return cout << "wrong1" << endl,0;
return 0;
}*/
/*
Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO
Read the statement CAREFULLY !!
Make a GREADY APPROACH !!!! (start from highest / lowest)
Make your own TESTS !!
Be careful from CORNER CASES !
*/
