#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
static int A[5000];
namespace {
const int MAX_N = 5e3 + 10;
int result, lowest, highest;
int ans[MAX_N];
int findFromRight(int l, int r, int diff) {
int res = -1;
int leftmost = l;
while(l <= r) {
int mid = (l + r) / 2;
if(query(leftmost, mid) == diff) {
res = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
return res;
}
int findFromLeft(int l, int r, int diff) {
int res = -1;
int rightmost = r;
while(l <= r) {
int mid = (l + r) / 2;
if(query(mid, rightmost) == diff) {
res = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
return res;
}
void solveLeft(int l, int r, bool state) {
if(l >= r) {
return;
}
int diff = query(l, r);
int res = findFromLeft(l, r, diff);
if(state == false) {
ans[res] = ans[r] + diff;
}
else {
ans[res] = ans[r] - diff;
}
solveLeft(l, res, state ^ true);
solveLeft(res + 1, r, state);
}
void solveRight(int l, int r, bool state) {
if(l >= r) {
return;
}
int diff = query(l, r);
int res = findFromRight(l, r, diff);
if(state == false) {
ans[res] = ans[l] + diff;
}
else {
ans[res] = ans[l] - diff;
}
solveRight(l, res - 1, state);
solveRight(res, r, state ^ true);
}
void solveMiddle(int l, int r, bool state) {
if(l >= r) {
return;
}
int diff = query(l, r);
int res = findFromRight(l, r, diff);
if(state == false) {
ans[res] = ans[l] + diff;
}
else {
ans[res] = ans[l] - diff;
}
solveMiddle(l, res - 1, state);
solveMiddle(res, r, state ^ true);
}
}
void solve(int N) {
// Find the highest pitch
result = findFromRight(1, N, N - 1);
ans[result] = N;
highest = result;
// Find the lowest pitch
result = findFromLeft(1, highest, N - 1);
ans[result] = 1;
lowest = result;
// Solve
solveLeft(1, lowest, false);
solveRight(highest, N, true);
solveMiddle(lowest, highest - 1, false);
// Answer
for(int i = 1; i <= N; i++) {
answer(i, ans[i]);
}
}
