#include <bits/stdc++.h>
#include "xylophone.h"
#define DIM 5010
using namespace std;
int v[DIM],a[DIM],f[DIM];
int n,i,pas;
/*
void answer (int i, int val){
//cout<<i<<" "<<val<<"\n";
cout<<val<<"\n";
}
int query (int x, int y){
pas++;
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 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);
*/
f[n] = 1;
if (sol_poz > 1){
v[sol_poz-1] = n - query (sol_poz-1,sol_poz);
f[v[sol_poz-1]] = 1;
}
if (sol_poz < n){
v[sol_poz+1] = n - query (sol_poz,sol_poz+1);
f[v[sol_poz+1]] = 1;
}
for (i=sol_poz-2;i>=1;i--){
int dif = query (i,i+1);
if (v[i+1] - dif <= 0){
v[i] = v[i+1] + dif;
f[v[i]] = 1;
continue;
}
if (v[i+1] + dif > n){
v[i] = v[i+1] - dif;
f[v[i]] = 1;
continue;
}
if (!f[v[i+1]-dif] && !f[v[i+1]+dif]){ /// am doua variante posibile
int dif2 = query (i,i+2);
int val = v[i+1] + dif;
if (max(val,max(v[i+1],v[i+2])) - min (val,min(v[i+1],v[i+2])) == dif2)
v[i] = val;
else v[i] = v[i+1] - dif;
/*
if (dif2 == max(v[i+1],v[i+2]) - min(v[i+1],v[i+2])){
if (v[i+1] < v[i+2])
v[i] = v[i+1] + dif;
else v[i] = v[i-1] - dif;
} else {
if (dif2 == dif){
if (v[i+1] < v[i+2])
v[i] = v[i+1] + dif;
else v[i] = v[i+1] - dif;
} else {
if (v[i+1] < v[i+2])
v[i] = v[i+1] - dif;
else v[i] = v[i+1] + dif;
}
}
*/
f[v[i]] = 1;
continue;
}
if (!f[v[i+1]-dif]){
v[i] = v[i+1] - dif;
f[v[i]] = 1;
} else {
v[i] = v[i+1] + dif;
f[v[i]] = 1;
}
}
for (i=sol_poz+2;i<=n;i++){
int dif = query (i-1,i);
if (v[i-1] - dif <= 0){
v[i] = v[i-1] + dif;
f[v[i]] = 1;
continue;
}
if (v[i-1] + dif > n){
v[i] = v[i-1] - dif;
f[v[i]] = 1;
continue;
}
if (!f[v[i-1]-dif] && !f[v[i-1]+dif]){
int dif2 = query (i-2,i);
if (max(v[i-1]+dif,max(v[i-1],v[i-2])) - min(v[i-1]+dif,min(v[i-1],v[i-2])) == dif2)
v[i] = v[i-1] + dif;
else v[i] = v[i-1] - dif;
f[v[i]] = 1;
continue;
}
if (!f[v[i-1]-dif]){
v[i] = v[i-1] - dif;
f[v[i]] = 1;
} else {
v[i] = v[i-1] + dif;
f[v[i]] = 1;
}
}
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);
cout<<pas;
return 0;
}
*/
