#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9,N = 40001;
#include "floppy.h"
struct ST {
vector<pii> t;
ST(){}
ST(int nn) {
t.assign(4*nn+1,{-inf,0});
}
void update(int node,int l,int r,int p,pii v) {
if (l == r) {
t[node] = v;
return;
}
int m = (l+r) >> 1;
if (p <= m) update(2*node,l,m,p,v);
else update(2*node+1,m+1,r,p,v);
t[node] = max(t[2*node],t[2*node+1]);
}
pii query(int node,int l,int r,int L,int R) {
if (l > R || r < L) return {-inf,0};
if (l >= L && r <= R) return t[node];
int m = (l+r) >> 1;
return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
}
} st;
int n;
string msg;
void constructtree(int l,int r) {
int root = st.query(1,1,n,l,r).ss;
msg+='0';
if (root > l) constructtree(l,root-1);
msg+='1';
if (root < r) constructtree(root+1,r);
}
void read_array(int subtask_id, const std::vector<int> &v) {
n = big(v);
st = ST(n);
for (int i=1;i<=n;i++) st.update(1,1,n,i,{v[i-1],i});
constructtree(1,n);
save_to_floppy(msg);
}
int timer = 1;
vi edges[N];
string MSG;
vi match;
int deconstruct(int l,int r) {
int haha = match[l];
int sol = -1;
if (haha > l+1) {
sol = deconstruct(l+1,haha-1);
}
int me = timer++;
if (haha > l+1) {
edges[me].push_back(sol);
}
if (haha < r) {
int sag = deconstruct(haha+1,r);
edges[me].push_back(sag);
}
return me;
}
int tin[N],tout[N],up[N][18];
void dfs(int node,int p) {
tin[node] = timer++;
up[node][0] = p;
for (int i=1;i<18;i++) up[node][i] = up[up[node][i-1]][i-1];
for (auto it : edges[node]) {
if (it != p) dfs(it,node);
}
tout[node]= timer++;
}
bool anc(int a,int b){
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a,int b) {
if (anc(a,b)) return a;
if (anc(b,a)) return b;
for (int i = 17;i>=0;i--) {
if (!anc(up[a][i],b)) a = up[a][i];
}
return up[a][0];
}
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
MSG = bits;
int q = big(a);
match.resize(big(bits));
stack<int> stk;
for (int i = 0;i<big(bits);i++) {
if (bits[i] == '0') {
stk.push(i);
}else {
match[stk.top()] = i;
stk.pop();
}
}
int root = deconstruct(0,big(MSG)-1);
timer = 1;
dfs(root,root);
vi ans(q);
for (int i = 0;i<q;i++) {
ans[i] = lca(a[i]+1,b[i]+1);
}
return ans;
}
