#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 5e3 + 7;
bool dd[mxN];
int a[mxN], dif[mxN];
int Check(int j, int n)
{
if (j <= 0 || j > n || dd[j])
return 0;
return j;
}
void solve(int n)
{
int l = 1, r = n, vt = 0;
while (l < r)
{
int mid = (l + r) / 2;
int tmp = query(1, mid);
if (tmp == n - 1)
{
vt = mid;
r = mid - 1;
}
else
l = mid + 1;
}
dd[n] = 1;
a[vt] = n;
for (int i = vt + 1; i <= n; i++)
{
dif[i] = query(i - 1, i);
if (Check(a[i - 1] - dif[i], n) && Check(a[i - 1] + dif[i], n))
{
int tmp = query(i - 2, i);
if (tmp == dif[i] + dif[i - 1])
a[i] = a[i - 2] - (a[i - 2] - a[i - 1]) / dif[i - 1] * dif[i];
else
a[i] = a[i - 1] - (a[i - 1] - a[i - 2]) / dif[i - 1] * dif[i];
}
else
a[i] = max(Check(a[i - 1] - dif[i], n), Check(a[i - 1] + dif[i], n));
dd[a[i]] = 1;
}
for (int i = vt - 1; i >= 1; i--)
{
dif[i] = query(i, i + 1);
if (Check(a[i + 1] - dif[i], n) && Check(a[i + 1] + dif[i], n))
{
int tmp = query(i, i + 2);
if (tmp == dif[i] + dif[i + 1])
a[i] = a[i + 2] - (a[i + 2] - a[i + 1]) / dif[i + 1] * dif[i];
else
a[i] = a[i + 1] - (a[i + 1] - a[i + 2]) / dif[i + 1] * dif[i];
}
else
a[i] = max(Check(a[i + 1] - dif[i], n), Check(a[i + 1] + dif[i], n));
dd[a[i]] = 1;
}
for (int i = 1; i <= n; i++)
answer(i, a[i]);
}
