#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;
bool small = 1;
for(int i = pos + 1, prev = -1; i <= N; ++i){
int ask = query(pos, i);
if(prev ^ ask){
ans[i] = ask + 1;
}
prev = ask;
}
for(int i = pos + 1, prev_idx = pos, prev = -1; i <= N; ++i){
int ask = query(prev_idx, i);
if(ans[i]){
small = 0;
prev_idx = i;
continue;
}
if(prev ^ ask){
if(small) ans[i] = ask + ans[prev_idx];
else ans[i] = ans[prev_idx] - ask;
prev = ask;
}else{
prev_idx = i - 1;
--i;
small ^= 1;
prev = -1;
}
}
for(int i = pos - 1, prev = -1; i >= 1; --i){
int ask = query(i, pos);
if(prev ^ ask){
ans[i] = ask + 1;
}
prev = ask;
}
small = 1;
for(int i = pos - 1, prev_idx = pos, prev = -1; i >= 1; --i){
int ask = query(i, prev_idx);
if(ans[i]){
small = 0;
prev_idx = i;
continue;
}
if(prev ^ ask){
if(small) ans[i] = ask + ans[prev_idx];
else ans[i] = ans[prev_idx] - ask;
prev = ask;
}else{
prev_idx = i - 1;
++i;
small ^= 1;
prev = -1;
}
}
for(int i = 1; i <= N; i++) {
answer(i, ans[i]);
//cout << ans[i] << " ";
}
}
