#include <bits/stdc++.h>
#include "xylophone.h"
#define MAX_N 5000
using namespace std;
int A[MAX_N + 1];
#ifdef local
int query(int s, int t)
{
int mn = 5000;
int mx = 1;
for(int i = s; i <= t; i ++)
{
mn = min(mn, A[i]);
mx = max(mx, A[i]);
}
return mx - mn;
}
#endif // local
int n;
int cautBin()
{
int i = 0;
int pas = 1 << 12;
while(pas != 0)
{
if(i + pas < n && query(1, i + pas) != n - 1)
i += pas;
pas >>= 1;
}
return i + 1;
}
int v[MAX_N + 1];
int diff[MAX_N + 1];
int ap[MAX_N + 1];
void baga(int st, int dr, int pas)
{
for(int i = st; i != dr + pas; i += pas)
{
int sign = 0;
int x = (i - pas < i ? query(i - pas, i) : query(i, i - pas));
if(v[i - pas] + x >= n || ap[v[i - pas] + x] == 1)
sign = -1;
else
if(v[i - pas] - x < 1 || ap[v[i - pas] - x] == 1)
sign = 1;
else
{
int y = (i - 2*pas < i ? query(i - 2*pas, i) : query(i, i - 2*pas));
if(y == diff[i - pas])
sign = (v[i - 2*pas] < v[i - pas] ? -1 : 1);
else
if(y == x + diff[i - pas])
sign = (v[i - pas] < v[i - 2*pas] ? -1 : 1);
else if(y == x)
sign = (v[i - pas] > v[i - 2*pas] ? -1 : 1);
}
diff[i] = x;
v[i] = v[i - pas] + x * sign;
ap[v[i]] = 1;
}
}
#ifdef local
void answer(int i, int nr)
{
if(nr != A[i])
{
cout << "PE POZ " << i << " ESTE " << A[i] << " TIU ZCICI " << nr << "\n";
exit(0);
}
// cout << " PE " << i << " " << nr << " == " << A[i] << "\n";
}
#endif // local
void solve(int N)
{
n = N;
int poz = cautBin();
v[poz] = n;
ap[v[poz]] = 1;
if(poz + 1 <= n)
{
v[poz + 1] = n - query(poz, poz + 1);
diff[poz + 1] = v[poz] - v[poz + 1];
ap[v[poz + 1]] = 1;
if(poz + 2 <= n)
baga(poz + 2, n, 1);
}
if(poz - 1 >= 1)
{
v[poz - 1] = n - query(poz - 1, poz);
diff[poz - 1] = v[poz] - v[poz - 1];
ap[v[poz - 1]] = 1;
if(poz - 2 >= 1)
baga(poz - 2, 1, -1);
}
for(int i = 1; i <= n; i ++)
answer(i, v[i]);
}
