#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using ii = tuple<int, int>;
using vii = vector<ii>;
constexpr int iINF = numeric_limits<int>::max();
constexpr ll lINF = numeric_limits<ll>::max();
template <typename T>
void DBG(T&& arg) {
cerr << arg << '\n';
}
template <typename T, typename... Ts>
void DBG(T&& x, Ts&&... y) {
cerr << x << ' ';
DBG(y...);
}
static vector<vi> qcache;
int queries;
int q(int l, int r) {
if (l > r) swap(l, r);
int Q;
if (l == r) Q = 0;
else {
if (qcache[l][r] == -1) queries++;
Q = (qcache[l][r] != -1)? qcache[l][r]: (qcache[l][r] = query(l, r));
}
DBG("query:", l, r, "V:", Q);
return Q;
}
// finds a2
int get_next(int a0, int a1, int q02, int q12) {
int a2;
int q01 = abs(a1 - a0);
if (q01 == q02) {
DBG("WOOF");
// minmax didnt change => ai2 between ai0 and ai1
if (a0 < a1) a2 = a1 - q12;
else a2 = a1 + q12;
} else {
DBG("MIAUW");
if (a0 < a1) {
if (q12 >= q02) a2 = a1 - q12;
else a2 = a1 + q12;
} else {
if (q12 == q02) a2 = a1 + q12;
else if (q12 < q02) a2 = a1 - q12;
else a2 = a1 + q12;
}
}
return a2;
}
void solve(int N) {
qcache.clear();
qcache.resize(N+1, vi(N+1, -1));
queries = 0;
vi ans(N+1);
ans[2] = q(1, 2);
for (int i = 1; i+2 <= N; ++i) {
int i0=i;
int i1=i+1;
int i2=i+2;
int q02 = q(i0, i2);
int q12 = q(i1, i2);
ans[i2] = get_next(ans[i0], ans[i1], q02, q12);
}
DBG(queries);
auto [mi, ma] = minmax_element(ans.begin()+1, ans.end());
if (mi < ma) {
DBG("good first guess");
int offset = N - *ma;
for (int i = 1; i <= N; ++i) {
DBG(offset + ans[i]);
answer(i, ans[i] + offset);
}
} else {
DBG("bad first guess");
int offset = *ma + 1;
for (int i = 1; i <= N; ++i) {
DBG(offset - ans[i]);
answer(i, offset - ans[i]);
}
}
}
