//#define _CRT_SECURE_NO_WARNINGS
//#include "grader.cpp"
#include "xylophone.h"
using namespace std;
#include <vector>
#include <bitset>
#include <map>
typedef vector<int16_t> vi;
typedef pair<int16_t, int16_t> pii;
map<pii, int16_t> queries;
int16_t ownQuery(int16_t a, int16_t b)
{
if (queries.find({ a, b }) != queries.end())
{
return queries[{a, b}];
}
return queries[{a, b}] = query(a, b);
}
void queryAndProcess(const int16_t& i, const int16_t& d, bool& canProgress, const int16_t& N, bitset<5001>& notFound, vi& values, const bool& doExtra)
{
if (i + d > N || i + d <= 0) return;
if (values[i] == -1) return;
if (values[i + d] != -1) return;
int16_t v = d > 0 ? ownQuery(i, i + d) : ownQuery(i + d, i);
int16_t opt1 = values[i] + v;
int16_t opt2 = values[i] - v;
int16_t result = 0; // 1 = opt1, 2 = opt2, 0 is unknown
if (opt1 < 1) result = 2;
else if (opt2 < 1) result = 1;
else if (opt1 > N) result = 2;
else if (opt2 > N) result = 1;
else if (!notFound[opt1]) result = 2;
else if (!notFound[opt2]) result = 1;
if (result == 0)
{
if (!doExtra) return;
int16_t v2 = d > 0 ? query(i - d, i + d) : query(i + d, i - d);
int16_t ma = max(values[i - d], values[i]);
int16_t mi = min(values[i - d], values[i]);
int16_t v2Opt1 = max(opt1, ma) - min(opt1, mi);
int16_t v2Opt2 = max(opt2, ma) - min(opt2, mi);
result = v2 == v2Opt1 ? 1 : 2;
}
if (result == 1)
{
values[i + d] = opt1;
notFound[opt1] = false;
}
else
{
values[i + d] = opt2;
notFound[opt2] = false;
}
canProgress = true;
}
void solve(int N)
{
int16_t a = 1, b = N;
while (a < b)
{
int16_t k = (a + b) / 2;
int16_t value = ownQuery(1, k);
if (value == N - 1) b = k;
else a = k + 1;
}
int16_t maxIndex = a;
a = 1, b = maxIndex - 1;
while (a < b)
{
int16_t k = (a + b + 1) / 2;
int16_t value = ownQuery(k, maxIndex);
if (value == N - 1) a = k;
else b = k - 1;
}
int16_t oneIndex = a;
bitset<5001> notFound;
for (int16_t i = 2; i < N; i++) notFound[i] = true;
vi values(N + 1, -1);
values[oneIndex] = 1;
values[maxIndex] = N;
bool canProgress = true;
while (canProgress)
{
canProgress = false;
for (int16_t i = 1; i <= N; i++)
{
queryAndProcess(i, -1, canProgress, N, notFound, values, false);
queryAndProcess(i, 1, canProgress, N, notFound, values, false);
if (notFound.none()) break;
}
}
canProgress = !notFound.none();
while (canProgress)
{
canProgress = false;
for (int16_t i = 1; i <= N; i++)
{
queryAndProcess(i, -1, canProgress, N, notFound, values, true);
queryAndProcess(i, 1, canProgress, N, notFound, values, true);
if (notFound.none()) break;
}
}
for (int16_t i = 1; i <= N; i++)
{
if (values[i] == -1) throw;
answer(i, values[i]);
}
}
