#include <bits/stdc++.h>
using namespace std;
#include "floppy.h"
#define name "TENBAI"
#define fi first
#define se second
// #define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 4e4 + 5;
vector<int> g[NM];
string res;
int n, dep[NM], up[NM][21];
pair<int, int> st[NM][21];
int get(int l, int r)
{
int L = __lg(r - l + 1);
return max(st[l][L], st[r - (1 << L) + 1][L]).se;
}
void dnc(int l, int r)
{
int m = get(l, r);
if (l <= m - 1)
{
res += '1';
dnc(l, m - 1);
}
else
res += '0';
if (m + 1 <= r)
{
res += '1';
dnc(m + 1, r);
}
else
res += '0';
}
void read_array(int _, const vector<int>& v)
{
n = v.size();
for (int i = 1; i <= n; i++)
st[i][0] = {v[i - 1], i};
for (int i = 1; (1 << i) <= n; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
st[j][i] = max(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);
dnc(1, n);
// cout << res << endl;
save_to_floppy(res);
}
int p = 0;
pair<int, int> build(int c)
{
int u = c + 1, cnt = 1;
if (res[p++] == '1')
{
auto t = build(c);
u += t.se;
g[u].push_back(t.fi);
up[t.fi][0] = u;
c += t.se;
cnt += t.se;
}
c++;
if (res[p++] == '1')
{
auto t = build(c);
g[u].push_back(t.fi);
up[t.fi][0] = u;
cnt += t.se;
}
return {u, cnt};
}
void dfs(int u)
{
for (int v : g[u])
{
dep[v] = dep[u] + 1;
dfs(v);
}
}
int lca(int u, int v)
{
if (dep[u] < dep[v])
swap(u, v);
int k = dep[u] - dep[v];
while (k)
u = up[u][__lg(k & -k)], k ^= k & -k;
if (u == v)
return u;
for (int i = __lg(n); i >= 0; i--)
if (up[u][i] != up[v][i])
u = up[u][i], v = up[v][i];
return up[u][0];
}
vector<int> solve_queries(int _, int N, const string& bits, const vector<int>& a, const vector<int>& b)
{
n = N;
res = bits;
int root = build(0).fi;
dfs(root);
for (int i = 1; (1 << i) <= n; i++)
for (int j = 1; j <= n; j++)
up[j][i] = up[up[j][i - 1]][i - 1];
vector<int> ans;
for (int i = 0; i < (int)a.size(); i++)
ans.push_back(lca(a[i] + 1, b[i] + 1) - 1);
return ans;
}
