#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
#define ALL(arr) begin(arr), end(arr)
#define CONTAINS(arr, val) (find(begin(arr), end(arr), val) != end(arr))
vector<vector<int>> poss;
vector<int> found;
vector<int> foundvals;
int binSearch(int bot, int top, int diff) {
int mid;
int low = bot, high = top;
while (low != high) {
mid = (low+high)/2;
int res = high;
if (mid != high)
res = query(bot, mid);
if (res == diff) high = mid;
else low = mid+1;
}
return low;
}
void solve(int N) {
poss.resize(N+1);
int n = 1;
int res = binSearch(1, N, N-1);
poss[res] = {N};
found.push_back(res);
answer(res, N);
foundvals.push_back(N);
while (n < N) {
int tmp = 0;
for (int iii = 0; iii < found.size(); iii++) {
int i = found[iii];
if (i != N && poss[i+1].size() == 0) {
tmp++;
int low, high;
int diff = query(i, i+1);
low = poss[i][0]-diff, high = poss[i][0]+diff;
int c = 0;
if (low >= 1 && !CONTAINS(foundvals, low)) {
c++;
poss[i+1].push_back(low);
}
if (high <= N && !CONTAINS(foundvals, high)) {
c++;
poss[i+1].push_back(high);
}
if (c == 1) {
answer(i+1, poss[i+1][0]);
found.push_back(i+1);
foundvals.push_back(poss[i+1][0]);
n++;
}
}
if (i != 1 && poss[i-1].size() == 0) {
tmp++;
int low, high;
int diff = query(i-1, i);
low = poss[i][0]-diff, high = poss[i][0]+diff;
int c = 0;
if (low >= 1 && !CONTAINS(foundvals, low)) {
c++;
poss[i-1].push_back(low);
}
if (high <= N && !CONTAINS(foundvals, high)) {
c++;
poss[i-1].push_back(high);
}
if (c == 1) {
answer(i-1, poss[i-1][0]);
found.push_back(i-1);
foundvals.push_back(poss[i-1][0]);
n++;
}
}
}
if (!tmp) {
for (int iii = 0; iii < found.size(); iii++) {
int i = found[iii];
if (i != 1 && i != N && (poss[i-1].size() > 1 ^ poss[i+1].size() > 1)) {
bool below = poss[i-1].size() > 1;
int res = query(i-1, i+1);
int i0 = i + (below ? 1 : -1);
int i0i = abs(poss[i][0] - poss[i + (below ? 1 : -1)][0]);
int ii1 = abs(poss[i][0] - poss[i + (below ? -1 : 1)][0]);
int corr;
if (res == i0i || ii1 == res) {
if (poss[i0][0] > poss[i][0])
corr = max(poss[i + (below ? -1 : 1)][0], poss[i + (below ? -1 : 1)][1]);
else corr = min(poss[i + (below ? -1 : 1)][0], poss[i + (below ? -1 : 1)][1]);
}
else {
if (poss[i0][0] > poss[i][0])
corr = min(poss[i + (below ? -1 : 1)][0], poss[i + (below ? -1 : 1)][1]);
else corr = max(poss[i + (below ? -1 : 1)][0], poss[i + (below ? -1 : 1)][1]);
}
poss[i + (below ? -1 : 1)].clear();
poss[i + (below ? -1 : 1)].push_back(corr);
foundvals.push_back(corr);
found.push_back(i + (below ? -1 : 1));
answer(i + (below ? -1 : 1), corr);
n++;
break;
}
}
}
}
}
