#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 5069;
int a[MAX];
bitset<MAX> used;
void solve(int n)
{
int l = 1, r = n-1;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (query(mid, n) == n-1) l = mid;
else r = mid - 1;
}
a[l] = 1; used[a[l]] = true;
if (l-1 >= 1)
{
int x = query(l-1, l);
a[l-1] = 1 + x; used[a[l-1]] = true;
}
if (l+1 <= n)
{
int x = query(l, l+1);
a[l+1] = 1 + x; used[a[l+1]] = true;
}
const auto valid = [&](int i) -> bool
{
return 1 <= i && i <= n;
};
for (int i = l-2; i >= 1; --i)
{
int y = query(i, i+1);
bool p = false, q = false;
if (valid(a[i+1] - y) && !used[a[i+1] - y])
p = true;
if (valid(a[i+1] + y) && !used[a[i+1] + y])
q = true;
if (p && q)
{
int x = query(i, i+2), z = abs(a[i+1] - a[i+2]);
if (x == z)
{
if (a[i+2] > a[i+1]) a[i] = a[i+1] + y;
else a[i] = a[i+1] - y;
}
else
{
if (a[i+2] > a[i+1])
{
if (x == y+z) a[i] = a[i+1] - y;
else a[i] = a[i+2] + (x-z);
}
else
{
if (x == y+z) a[i] = a[i+1] + y;
else a[i] = a[i+2] - (x-z);
}
}
}
else if (p) a[i] = a[i+1] - y;
else a[i] = a[i+1] + y;
used[a[i]] = true;
}
for (int i = l+2; i <= n; ++i)
{
int y = query(i-1, i);
bool p = false, q = false;
if (valid(a[i-1] - y) && !used[a[i-1] - y])
p = true;
if (valid(a[i-1] + y) && !used[a[i-1] + y])
q = true;
if (p && q)
{
int x = query(i-2, i), z = abs(a[i-2] - a[i-1]);
if (x == z)
{
if (a[i-2] > a[i-1]) a[i] = a[i-1] + y;
else a[i] = a[i-1] - y;
}
else
{
if (a[i-2] > a[i-1])
{
if (x == y+z) a[i] = a[i-1] - y;
else a[i] = a[i-2] + (x-z);
}
else
{
if (x == y+z) a[i] = a[i-1] + y;
else a[i] = a[i-2] - (x-z);
}
}
}
else if (p) a[i] = a[i-1] - y;
else a[i] = a[i-1] + y;
used[a[i]] = true;
}
// for (int i = 1; i <= n; ++i)
// cerr << a[i] << " \n"[i == n];
for (int i = 1; i <= n; ++i)
answer(i, a[i]);
}
