#include <bits/stdc++.h>
#include "xylophone.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define NMAX 1000005
using namespace std;
// static const int N_MAX = 5000;
// static const int Q_MAX = 10000;
// static int N;
// static int A[N_MAX];
// static bool used[N_MAX];
// static int query_c;
// static int answer_c;
// int query(int s, int t) {
// if(query_c >= Q_MAX) {
// printf("Wrong Answer\n");
// exit(0);
// }
// query_c++;
// if(!(1 <= s && s <= t && t <= N)) {
// printf("Wrong Answer\n");
// exit(0);
// }
// int mx = 0, mn = N + 1;
// for(int i = s - 1; i < t; i++) {
// if(mx < A[i]) {
// mx = A[i];
// }
// if(mn > A[i]) {
// mn = A[i];
// }
// }
// return mx - mn;
// }
// void answer(int i, int a) {
// cout << a << " oldu" << endl;
// answer_c++;
// if(!(1 <= i && i <= N)) {
// printf("Wrong Answerwww\n");
// exit(0);
// }
// if(!(1 <= a && a <= N)) {
// printf("Wrong Answerqqqq\n");
// exit(0);
// }
// if(used[i - 1]) {
// printf("Wrong Answerasd\n");
// exit(0);
// }
// if(a != A[i - 1]) {
// printf("Wrong Answerrrr\n");
// exit(0);
// }
// used[i - 1] = true;
// }
int a[NMAX], v[NMAX];
void solve(int n) {
int i = 1;
while(query(i, n) == n - 1)i++;i--;
answer(i, 1);
a[i] = 1;
v[1] = 1;
// cout << i << endl;
if(i > 1){
int cvp = query(i - 1, i);
answer(i - 1, cvp + 1);
a[i - 1] = cvp + 1;
v[cvp + 1] = 1;
}
if(i < n){
int cvp = query(i, i + 1);
answer(i + 1, cvp + 1);
a[i + 1] = cvp + 1;
v[cvp + 1] = 1;
}
for(int j = i - 2; j >= 1; j--){
int x = query(j, j + 2);
int y = query(j, j + 1);
int aa = a[j + 1];
int bb = a[j + 2];
int mx = max(aa, bb);
int mn = min(aa, bb);
// int z = mx - mn;
int dur = 0;
int p1 = aa + y;
int p2 = aa - y;
int son = -1;
if(max(mx, p1) - min(mn, p1) != x)
son = p2;
if(max(mx, p2) - min(mn, p2) != x)
son = p1;
assert(son != -1);
answer(j, son);
a[j] = son;
v[son] = 1;
}
for(int j = i + 2; j <= n; j++){
int x = query(j - 2, j);
int y = query(j - 1, j);
int aa = a[j - 1];
int bb = a[j - 2];
int mx = max(aa, bb);
int mn = min(aa, bb);
// int z = mx - mn;
int dur = 0;
int p1 = aa + y;
int p2 = aa - y;
int son = -1;
if(max(mx, p1) - min(mn, p1) != x)
son = p2;
if(max(mx, p2) - min(mn, p2) != x)
son = p1;
assert(son != -1);
answer(j, son);
a[j] = son;
v[son] = 1;
}
}
// int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// query_c = 0;
// answer_c = 0;
// if(scanf("%d", &N) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// for(int i = 0; i < N; i++) {
// if(scanf("%d", A + i) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// used[i] = false;
// }
// solve(N);
// if(!(answer_c == N)) {
// printf("Wrong Answer\n");
// exit(0);
// }
// printf("Accepted : %d\n", query_c);
// }
