#include<bits/stdc++.h>
#include "floppy.h"
using namespace std;
const int maxn=40005;
const int maxl=20;
#define pii pair<int,int>
#define fi first
#define se second
void read_array(int subtask_id, const std::vector<int> &v) {
string bits;
int n=(int)v.size();
vector<int> lt(n),rt(n),x;
for(int i=0;i<n;i++){
while(!x.empty() && v[x.back()]<v[i]) x.pop_back();
lt[i]=(x.empty()?0:x.back()+1);
x.push_back(i);
}
x.clear();
for(int i=n-1;i>=0;i--){
while(!x.empty() && v[x.back()]<v[i]) x.pop_back();
rt[i]=(x.empty()?n-1:x.back()-1);
x.push_back(i);
}
map<pii,int> mp;
for(int i=0;i<n;i++) mp[{lt[i],rt[i]}]=i;
int root=-1;
vector<int> lc(n,-1),rc(n,-1);
for(int i=0;i<n;i++){
if(lt[i]<i) lc[i]=(mp[{lt[i],i-1}]);
if(i<rt[i]) rc[i]=(mp[{i+1,rt[i]}]);
if(lt[i]==0 && rt[i]==n-1) root=i;
}
function<void(int)> dfs = [&](int u){
if(u==-1){
bits+='0';
return;
}
if(u!=root) bits+='1';
dfs(lc[u]);
dfs(rc[u]);
};
dfs(root);
save_to_floppy(bits);
}
std::vector<int> solve_queries(int subtask_id, int n,
const std::string &bit,
const std::vector<int> &a, const std::vector<int> &b) {
int m=(int)a.size();
vector<int> res(m,-1),lc(n,-2),rc(n,-2);
int pos=0;
stack<int> s;
vector<int> ind(n,-1),f(n,-1),dep(n,0);
vector<vector<int>> par(n,vector<int>(maxl,-1));
string bits="1"+bit;
for(char c:bits){
while(!s.empty() && (lc[s.top()]!=-2 && rc[s.top()]!=-2)) s.pop();
if(c=='1'){
if(!s.empty()){
int u=s.top();
if(lc[u]==-2) lc[u]=pos;
else rc[u]=pos;
}
s.push(pos++);
}
else{
int u=s.top();
if(lc[u]==-2) lc[u]=-1;
else rc[u]=-1;
}
}
int cnt=0;
function<void(int)> dfs = [&](int u){
if(lc[u]!=-1){
dep[lc[u]]=dep[u]+1;
par[lc[u]][0]=u;
dfs(lc[u]);
}
f[cnt]=u;
ind[u]=cnt++;
if(rc[u]!=-1){
dep[rc[u]]=dep[u]+1;
par[rc[u]][0]=u;
dfs(rc[u]);
}
};
dfs(0);
for(int i=1;i<maxl;i++){
for(int u=0;u<n;u++) if(par[u][i-1]!=-1) par[u][i]=par[par[u][i-1]][i-1];
}
auto lca = [&](int u,int v){
if(dep[u]>dep[v]) swap(u,v);
for(int i=0;i<maxl;i++) if((dep[v]-dep[u])>>i&1) v=par[v][i];
if(u==v) return u;
for(int i=maxl-1;i>=0;i--){
if(par[u][i]!=par[v][i]){
u=par[u][i];
v=par[v][i];
}
}
return par[u][0];
};
for(int i=0;i<m;i++){
int A=f[a[i]];
int B=f[b[i]];
res[i]=ind[lca(A,B)];
}
return res;
}
