#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
void solve(int N) {
vector<int> ans(N + 1, 0);
int res = query(1, N), pos = -1, st = 1, en = N;
while(st <= en){
int mid = st + (en - st) / 2;
if(query(mid, N) == res){
pos = mid;
st = mid + 1;
}else{
en = mid - 1;
}
}
ans[pos] = 1;
set<int> seen;
if(pos - 1 >= 1){
ans[pos - 1] = query(pos - 1, pos) + 1;
seen.insert(ans[pos - 1]);
}
if(pos + 1 <= N){
ans[pos + 1] = query(pos, pos + 1) + 1;
seen.insert(ans[pos + 1]);
}
for(int i = pos + 2; i <= N; ++i){
int X = query(i - 1, i);
if(seen.find(ans[i - 1] + X) != seen.end() || (ans[i - 1] + X) > N){
ans[i] = ans[i - 1] - X;
seen.insert(ans[i]);
continue;
}
if(seen.find(ans[i - 1] - X) != seen.end() || (ans[i - 1] - X) <= 0){
ans[i] = ans[i - 1] + X;
seen.insert(ans[i]);
continue;
}
int a = ans[i - 2], b = ans[i - 1];
int z = min(ans[i - 1] - X, a);
int a2 = query(i - 2, i);
if(ans[i - 2] < ans[i - 1]){
if(a2 == ans[i - 1] - z){
ans[i] = ans[i - 1] - X;
}else{
ans[i] = ans[i - 1] + X;
}
}else{
if(ans[i - 2] - (ans[i - 1] - X) == a2){
ans[i] = ans[i - 1] - X;
}else{
ans[i] = ans[i - 1] + X;
}
}
seen.insert(ans[i]);
}
for(int i = pos - 2; i >= 1; --i){
int X = query(i, i + 1);
if(seen.find(ans[i + 1] + X) != seen.end() || (ans[i + 1] + X) > N){
ans[i] = ans[i + 1] - X;
seen.insert(ans[i]);
continue;
}
if(seen.find(ans[i + 1] - X) != seen.end() || (ans[i + 1] - X) <= 0){
ans[i] = ans[i + 1] + X;
seen.insert(ans[i]);
continue;
}
int a = ans[i + 2], b = ans[i + 1];
int z = min(ans[i + 1] - X, a);
int a2 = query(i, i + 2);
if(ans[i + 2] < ans[i + 1]){
if(a2 == ans[i + 1] - z){
ans[i] = ans[i + 1] - X;
}else{
ans[i] = ans[i + 1] + X;
}
}else{
if(ans[i + 2] - (ans[i + 1] - X) == a2){
ans[i] = ans[i + 1] - X;
}else{
ans[i] = ans[i + 1] + X;
}
}
seen.insert(ans[i]);
}
for(int i = 1; i <= N; i++) {
answer(i, ans[i]);
//cout << ans[i] << " ";
}
}
