#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#define all(a) a.begin(),a.end()
using namespace std;
#include "popa.h"
int solve(int n, int* l, int* r) {
for (int i = 0; i < n; i++) {
l[i] = -1;
r[i] = -1;
}
int pr[n] = {};
fill(pr, pr + n, -1);
int re = 0;
for (int i = 1; i < n; i++) {
int u = i - 1;
bool ch = 0;
while (1) {
if (r[u] == -1) {
if (query(u, u, u, i)) {
r[u] = i;
pr[i] = u;
ch = 1;
// cout << "? " << i << ' ' << u << endl;
break;
}
}
if (pr[u] == -1) {
break;
} else {
u = pr[u];
}
}
if (!ch) {
re = i;
l[i] = u;
pr[u] = i;
// cout << "? " << u << ' ' << i << endl;
}
// exit(0);
}
// for (int i = 0; i < n; i++) {
// cout << l[i] << ' ';
// }
// cout << endl;
// for (int i = 0; i < n; i++) {
// cout << r[i] << ' ';
// }
// cout << endl;
// exit(0);
return re;
}
