#include <bits/stdc++.h>
#include <stdlib.h>
#include <string.h>
#include "floppy.h"
// #include "grader.cpp"
using namespace std;
const int MXN = 1e5 + 10, LG = 18;
int n, sp[MXN][LG], par[MXN][LG], h[MXN], pos[MXN], tme, cur, lc[MXN], rc[MXN], rev[MXN];
vector<int> arr, order;
string bits;
int get(int l, int r){
int lg = 31 - __builtin_clz(r - l + 1);
int i = sp[l][lg], j = sp[r - (1 << lg) + 1][lg];
if (arr[i] > arr[j]) return i;
return j;
}
void dnc(int l, int r){
if (l > r) return ;
int mx = get(l, r);
if (l == mx) bits += '0';
else bits += '1';
if (mx == r) bits += '0';
else bits += '1';
dnc(l, mx - 1);
dnc(mx + 1, r);
}
void read_array(int subtask_id, const vector<int> &v) {
arr = v;
n = arr.size();
for (int i = 0; i < n; i ++)
sp[i][0] = i;
for (int j = 1; j < LG; j ++){
for (int i = 0; i < n; i ++){
int nxt = i + (1 << (j - 1));
sp[i][j] = sp[i][j - 1];
if (nxt < n and arr[sp[i][j]] < arr[sp[nxt][j - 1]])
sp[i][j] = sp[nxt][j - 1];
}
}
dnc(0, n - 1);
save_to_floppy(bits);
}
void dfs(int v){
for (int j = 1; j < LG; j ++)
if (par[v][j - 1] != -1)
par[v][j] = par[par[v][j - 1]][j - 1];
if (bits[2 * v] == '1'){
cur++;
lc[v] = cur;
par[cur][0] = v;
h[cur] = h[v] + 1;
dfs(cur);
}
rev[tme] = v;
pos[v] = tme++;
if (bits[2 * v + 1] == '1'){
cur++;
rc[v] = cur;
par[cur][0] = v;
h[cur] = h[v] + 1;
dfs(cur);
}
}
int lca(int u, int v){
if (h[u] > h[v]) swap(u, v);
int d = h[v] - h[u];
for (int i = 0; i < LG; i ++)
if ((1 << i) & d)
v = par[v][i];
if (u == v) return v;
for (int i = LG - 1; i >= 0; i --)
if (par[u][i] != par[v][i])
u = par[u][i], v = par[v][i];
return par[v][0];
}
vector<int> solve_queries(int subtask_id, int nn,
const string &ss,
const vector<int> &a, const vector<int> &b) {
bits = ss, n = nn;
memset(par, -1, sizeof par);
dfs(0);
vector<int> answers;
for (int i = 0; i < a.size(); i ++){
int l = a[i], r = b[i];
int u = rev[l], v = rev[r];
int L = lca(u, v);
answers.push_back(pos[L]);
}
return answers;
}
