#include<bits/stdc++.h>
#include "floppy.h"
using namespace std;
const int mxn=1e5+10;
int n,id,node,table[mxn][20],depth[mxn],pos[mxn],val[mxn],up[20][mxn];
vector<int>arr;
string bits;
int get(int l,int r)
{
int lg=31-__builtin_clz(r-l+1);
int L=table[l][lg],R=table[r-(1<<lg)+1][lg];
if(arr[L]>arr[R])
return L;
return R;
}
void rec(int l,int r)
{
if(l>r)
return;
int mx=get(l,r);
if(l==mx)
bits+='0';
else
bits+='1';
if(r==mx)
bits+='0';
else
bits+='1';
rec(l,mx-1);
rec(mx+1,r);
}
void read_array(int subtask_id, const vector<int> &v)
{
arr=v;
n=(int)v.size();
for(int i=0;i<n;++i)
table[i][0]=i;
for(int j=1;j<20;++j)
{
for(int i=0;i<n;++i)
{
int nxt=i+(1<<(j-1));
table[i][j]=table[i][j-1];
if(nxt<n && arr[table[i][j]] < arr[table[nxt][j-1]])
table[i][j]=table[nxt][j-1];
}
}
rec(0,n-1);
save_to_floppy(bits);
}
void dfs(int u)
{
for(int i=1;i<20;i++)
if(~up[i-1][u])
up[i][u]=up[i-1][up[i-1][u]];
if(bits[u<<1]=='1')
{
node++;
up[0][node]=u;
depth[node]=depth[u]+1;
dfs(node);
}
val[u]=id;
pos[id]=u;
id++;
if(bits[u<<1|1]=='1')
{
node++;
up[0][node]=u;
depth[node]=depth[u]+1;
dfs(node);
}
}
int lca(int a,int b)
{
if(depth[a]<depth[b])
swap(a,b);
int need=depth[a]-depth[b];
for(int i=19;~i;--i)
{
if((1<<i)<=need)
{
need-=(1<<i);
a=up[i][a];
}
}
if(a==b)
return a;
for(int i=19;~i;--i)
if(up[i][a]!=up[i][b])
{
a=up[i][a];
b=up[i][b];
}
return up[0][a];
}
vector<int> solve_queries(int subtask_id, int N,
const string &ss,
const vector<int> &a, const vector<int> &b)
{
n=N;
bits=ss;
id=0,node=0;
memset(up,-1,sizeof(up));
dfs(0);
vector<int>ans;
for(int i=0;i<(int)a.size();i++)
{
int L,R;
L=pos[a[i]],R=pos[b[i]];
int lc=lca(L,R);
ans.emplace_back(val[lc]);
}
return ans;
}
