#include <stdlib.h>
#include <string.h>
#include "floppy.h"
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 4e4 + 4;
const int LG = 15;
int n, st[maxn][LG + 1];
string send;
vector<int> vl;
void calc(int l, int r) {
if (l > r) return;
auto get = [&](int l, int r) {
int p = 31 - __builtin_clz(r - l + 1);
return vl[st[l][p]] > vl[st[r - (1 << p) + 1][p]] ? st[l][p] : st[r - (1 << p) + 1][p];
};
int mid = get(l, r);
if (l <= mid - 1) {
send += '1';
calc(l, mid - 1);
} else {
send += '0';
}
if (mid + 1 <= r) {
send += '1';
calc(mid + 1, r);
} else {
send += '0';
}
}
void read_array(int subtask_id, const vector<int> &_v) {
vl = _v;
n = (int)vl.size();
vl.insert(vl.begin(), 0);
for (int i = 1; i <= n; ++i) {
st[i][0] = i;
}
send = "";
for (int j = 1; j <= LG; ++j) {
for (int i = 1; i + (1 << j) <= n + 1; ++i) {
if (vl[st[i][j - 1]] > vl[st[i + (1 << (j - 1))][j - 1]]) {
st[i][j] = st[i][j - 1];
} else {
st[i][j] = st[i + (1 << (j - 1))][j - 1];
}
}
}
calc(1, n);
save_to_floppy(send);
}
int up[maxn][LG + 1];
int child[maxn][2];
int h[maxn];
int num_nodes;
int id;
int rv[maxn];
int tin[maxn];
int mx[maxn];
void build(int u) {
for (int ite = 0; ite < 2; ++ite) {
if (send[id] == '1') {
++num_nodes;
++id;
child[u][ite] = num_nodes;
h[num_nodes] = h[u] + 1;
up[num_nodes][0] = u;
for (int i = 1; i <= LG; ++i) {
up[num_nodes][i] = up[up[num_nodes][i - 1]][i - 1];
}
build(num_nodes);
mx[u] = max(mx[u], mx[num_nodes] + 1);
} else ++id;
}
}
void construct(int u, int bl, int br) {
int p = bl;
if (child[u][0]) {
p = mx[child[u][0]] + bl + 1;
}
tin[p] = u, rv[u] = p;
if (child[u][0]) {
construct(child[u][0], bl, p - 1);
}
if (child[u][1]) {
construct(child[u][1], p + 1, br);
}
}
int lca(int u, int v) {
if (h[u] < h[v]) swap(u, v);
for (int i = LG; i >= 0; --i) {
if ((h[u] - h[v]) >> i & 1) {
u = up[u][i];
}
}
if (u == v) return u;
for (int i = LG; i >= 0; --i) {
if (up[u][i] != up[v][i]) {
u = up[u][i], v = up[v][i];
}
}
return up[v][0];
}
vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
send = bits;
debug(send);
n = N;
for (int i = 1; i <= n; ++i) {
h[i] = 0;
}
num_nodes = id = 0;
build(++num_nodes);
construct(1, 1, n);
vector<int> res;
// for (int i = 1; i <= n; ++i) {
// debug(i, rv[i], child[i][0], child[i][1]);
// }
for (int i = 0; i < (int)a.size(); ++i) {
res.push_back(rv[lca(tin[a[i] + 1], tin[b[i] + 1])] - 1);
}
debug(res);
return res;
}
