#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
map<ii, int> queries;
int q(int l, int h) {
if (l == h) return 0;
if (queries.find({l, h}) != queries.end()) {
return queries[{l, h}];
}
int res = query(l, h);
queries[{l, h}] = res;
return res;
}
void findNext2(int N, int top, int bot, int prevPitch, bool MIN);
void findNext1(int N, int top, int bot = 1, int prevPitch = 1, bool MIN = false, bool exl = false) {
if (top == bot) return;
int mid;
int low = bot, high = top;
int diff = q(low, high);
if (abs(top - bot) != 1) {
while (low != high) {
mid = (low+high)/2;
int res = q(bot, mid);
if (res == diff) high = mid;
else low = mid+1;
}
} else low = top;
answer(low, prevPitch+diff*(MIN?-1:1));
findNext1(N, top, low, prevPitch+diff*(MIN?-1:1), !MIN, true);
findNext2(N, low, bot + exl, prevPitch+diff*(MIN?-1:1), !MIN);
}
void findNext2(int N, int top, int bot, int prevPitch, bool MIN ) {
if (top == bot) return;
int mid;
int low = bot, high = top;
int diff = q(low, high);
if (abs(top - bot) != 1) {
while (low != high) {
mid = (low+high+1)/2;
int res = q(mid, top);
if (res == diff) low = mid;
else high = mid-1;
}
} else low = bot;
answer(low, prevPitch+diff*(MIN?-1:1));
findNext1(N, top-1, low, prevPitch+diff*(MIN?-1:1), !MIN, true);
findNext2(N, low, bot, prevPitch+diff*(MIN?-1:1), !MIN);
}
void solve(int N) {
findNext1(N, N);
}
