#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int N) {
vector<int> ans(N + 1), dif(N + 1);
for (int i = 1; i < N; i++)
dif[i] = query(i, i + 1);
int l = 1, r = N - 1;
while (l <= r)
{
int m = (l + r) / 2;
if (query(m, N) == N - 1)
l = m + 1;
else r = m - 1;
}
int one = r;
ans[one] = 1;
ans[one + 1] = 1 + dif[one];
ans[one - 1] = 1 + dif[one - 1];
vector<bool> v(N + 1);
v[1] = v[1 + dif[one]] = v[1 + dif[one - 1]] = true;
for (int i = 3; i <= N; i++)
{
if (ans[i]) continue;
if (!ans[i - 1]) continue;
v[ans[i]] = 1;
int x = dif[i - 2];
int y = dif[i - 1];
if (ans[i - 1] - y < 1 || v[ans[i - 1] - y])
{
ans[i] = ans[i - 1] + y;
continue;
}
if (ans[i - 1] + y > N || v[ans[i - 1] + y])
{
ans[i] = ans[i - 1] - y;
continue;
}
if (!ans[i - 2]) continue;
int z = query(i - 2, i);
if (ans[i - 2] < ans[i - 1])
{
if (z != x + y) ans[i] = ans[i - 1] - y;
else ans[i] = ans[i - 1] + y;
}
else
{
if (z != x + y) ans[i] = ans[i - 1] + y;
else ans[i] = ans[i - 1] - y;
}
}
for (int i = N - 2; i >= 1; i--)
{
if (ans[i]) continue;
if (!ans[i + 1]) continue;
v[ans[i]] = 1;
int x = dif[i + 1];
int y = dif[i];
if (ans[i + 1] - y < 1 || v[ans[i + 1] - y])
{
ans[i] = ans[i + 1] + y;
continue;
}
if (ans[i + 1] + y > N || v[ans[i + 1] + y])
{
ans[i] = ans[i + 1] - y;
continue;
}
if (!ans[i + 2]) continue;
int z = query(i, i + 2);
if (ans[i + 2] < ans[i + 1])
{
if (z != x + y) ans[i] = ans[i + 1] - y;
else ans[i] = ans[i + 1] + y;
}
else
{
if (z != x + y) ans[i] = ans[i + 1] + y;
else ans[i] = ans[i + 1] - y;
}
}
for (int i = 1; i <= N; i++)
answer(i, ans[i]);
}
