#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int N) {
int A[N+1], B[N+1];
A[1] = B[1] = 500069;
int maxa = 1, maxb = 1, mina = 1, minb = 1;
for (int i = 2; i <= N; i++) {
int q1 = query(i-1, i);
if (i == 2) {
A[2] = A[1] + q1;
B[2] = B[1] - q1;
} else {
int q2 = query(i-2, i);
if (A[i-2] < A[i-1]) {
if (q2 == q1 + A[i-1] - A[i-2]) {
A[i] = A[i-1] + q1;
B[i] = B[i-1] - q1;
} else {
A[i] = A[i-1] - q1;
B[i] = B[i-1] + q1;
}
} else {
if (q2 == q1 + A[i-2] - A[i-1]) {
A[i] = A[i-1] - q1;
B[i] = B[i-1] + q1;
} else {
A[i] = A[i-1] + q1;
B[i] = B[i-1] - q1;
}
}
}
mina = A[mina] > A[i] ? i : mina;
minb = B[minb] > B[i] ? i : minb;
maxa = A[maxa] < A[i] ? i : maxa;
maxb = B[maxb] < B[i] ? i : maxb;
}
if (mina < maxa) {
int sub = A[mina] - 1;
for (int i = 1; i <= N; i++) {
answer(i, A[i] - sub);
}
} else {
int sub = B[minb] - 1;
for (int i = 1; i <= N; i++) {
answer(i, B[i] - sub);
}
}
}
