#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
void solve(int n) {
int l = 0, r = n;
while (l + 1 < r) {
int m = (l + r) / 2;
if (query(1, m) == n - 1) {
r = m;
} else {
l = m;
}
}
vector<int> a(n + 1);
a[r] = n;
if (r + 1 <= n) {
a[r + 1] = n - query(r, r + 1);
}
if (r >= 2) {
a[r - 1] = n - query(r - 1, r);
}
for (int i = r + 2; i <= n; i++) {
int x = a[i - 2], y = a[i - 1];
int t = query(i - 2, i);
int s = query(i - 1, i);
if (x < y) {
if (t == y - x) {
a[i] = y - s;
} else if (s == t) {
a[i] = (2 * y - s - t) / 2;
} else {
a[i] = (t + s + x + y) / 2;
}
} else {
if (s == t) {
a[i] = y + s;
} else if (t == x - y) {
a[i] = y + s;
} else {
a[i] = (x + y - s - t) / 2;
}
}
}
for (int i = r - 2; i >= 1; i--) {
int x = a[i + 2], y = a[i + 1];
int t = query(i, i + 2);
int s = query(i, i + 1);
if (x < y) {
if (t == y - x) {
a[i] = y - s;
} else if (s == t) {
a[i] = (2 * y - s - t) / 2;
} else {
a[i] = (t + s + x + y) / 2;
}
} else {
if (s == t) {
a[i] = y + s;
} else if (t == x - y) {
a[i] = y + s;
} else {
a[i] = (x + y - s - t) / 2;
}
}
}
for (int i = 1; i <= n; i++) {
answer(i, a[i]);
}
}
