#include <bits/stdc++.h>
#include "xylophone.h"
#define DIM 5010
using namespace std;
int v[DIM],a[DIM];
int n,i;
/*
void answer (int i, int val){
cout<<i<<" "<<val<<"\n";
}
int query (int x, int y){
int maxi = 0, mini = n+1;
for (int i=x;i<=y;i++){
mini = min (mini,a[i]);
maxi = max (maxi,a[i]);
}
return maxi - mini;
}
*/
void divide (int st, int dr, int val, int tip, int capat){
if (st > dr)
return;
if (!tip){ /// am un mini, deci determin un maxi
int maxi,l,r,poz;
if (capat){
int dif = query (st,dr+1);
maxi = val + dif;
l = st, r = dr, poz = 0;
while (l <= r){
int mid = (l+r)>>1;
if (query (mid,dr+1) == dif){
poz = mid;
l = mid+1;
} else r = mid-1;
}
} else {
int dif = query (st-1,dr);
maxi = val + dif;
l = st, r = dr, poz = 0;
while (l <= r){
int mid = (l+r)>>1;
if (query (st-1,mid) == dif){
poz = mid;
r = mid-1;
} else l = mid+1;
}
}
v[poz] = maxi;
divide (st,poz-1,maxi,1,1);
divide (poz+1,dr,maxi,1,0);
} else {
int mini,l,r,poz;
if (capat){
int dif = query (st,dr+1);
mini = val - dif;
l = st, r = dr;
while (l <= r){
int mid = (l+r)>>1;
if (query(mid,dr+1) == dif){
l = mid+1;
poz = mid;
} else r = mid-1;
}
} else {
int dif = query (st-1,dr);
mini = val - dif;
l = st, r = dr;
while (l <= r){
int mid = (l+r)>>1;
if (query(st-1,mid) == dif){
r = mid-1;
poz = mid;
} else l = mid+1;
}
}
v[poz] = mini;
divide (st,poz-1,mini,0,1);
divide (poz+1,dr,mini,0,0);
}
}
void solve (int n){
/// determin pozitia lui n
int st = 1, dr = n, sol_poz;
while (st <= dr){
int mid = (st+dr)>>1;
if (query(1,mid) == n-1){
sol_poz = mid;
dr = mid-1;
} else st = mid+1;
}
v[sol_poz] = n;
divide (1,sol_poz-1,n,1,1);
divide (sol_poz+1,n,n,1,0);
for (int i=1;i<=n;i++)
answer (i,v[i]);
}
/*
int main (){
ifstream cin ("date.in");
ofstream cout ("date.out");
cin>>n;
for (i=1;i<=n;i++)
cin>>a[i];
solve (n);
return 0;
}
*/
