#include "xylophone.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <chrono>
#include <random>
typedef long long llong;
const int MAXN = 5000 + 10;
int a[MAXN];
bool isTaken[MAXN];
void solve(int n)
{
int l = 1, r = n, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (query(1, mid) < n - 1) l = mid;
else r = mid;
}
a[r] = n;
if (r > 1)
{
a[r - 1] = a[r] - query(r - 1, r);
isTaken[a[r - 1]] = true;
}
if (r < n)
{
a[r + 1] = a[r] - query(r, r + 1);
isTaken[a[r + 1]] = true;
}
isTaken[a[r]] = true;
for (int pos = r + 2 ; pos <= n ; ++pos)
{
int curr = query(pos - 1, pos);
if (a[pos - 1] - curr <= 0 || isTaken[a[pos - 1] - curr])
{
a[pos] = a[pos - 1] + curr;
continue;
}
if (a[pos - 1] - curr > n || isTaken[a[pos - 1] + curr])
{
a[pos] = a[pos - 1] - curr;
continue;
}
int all = query(pos - 2, pos);
if ((all == curr + abs(a[pos - 1] - a[pos - 2])) ^ (a[pos - 2] > a[pos - 1]))
{
a[pos] = a[pos - 1] + curr;
} else
{
a[pos] = a[pos - 1] - curr;
}
isTaken[a[pos]] = true;
}
for (int pos = r - 2 ; pos >= 1 ; --pos)
{
int curr = query(pos, pos + 1);
if (a[pos + 1] - curr <= 0 || isTaken[a[pos + 1] - curr])
{
a[pos] = a[pos + 1] + curr;
continue;
}
if (a[pos + 1] - curr > n || isTaken[a[pos + 1] + curr])
{
a[pos] = a[pos + 1] - curr;
continue;
}
int all = query(pos, pos + 2);
if ((all == curr + abs(a[pos + 1] - a[pos + 2])) ^ (a[pos + 2] > a[pos + 1]))
{
a[pos] = a[pos + 1] + curr;
} else
{
a[pos] = a[pos + 1] - curr;
}
isTaken[a[pos]] = true;
}
for (int i = 1 ; i <= n ; ++i)
{
answer(i, a[i]);
}
}
