#include<bits/stdc++.h>
#include <stdlib.h>
#include <string.h>
#include "floppy.h"
using namespace std;
int n,id=0,node=0;
vector<vector<int>>table(20,vector<int>(1e5+10)),up(1e5+10,vector<int>(20,0));
vector<int>depth(1e5+10),pos(1e5+10),val(1e5+10),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)
{
n=v.size();
arr=v;
bits.clear();
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)
{
int a=table[i][j-1],b=table[nxt][j-1];
table[i][j]=(arr[a]>arr[b])?a:b;
}
}
}
rec(0,n-1);
save_to_floppy(bits);
}
void dfs(int u)
{
for(int i=1;i<20;i++)
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 nn,const string &s,const vector<int>&a,const vector<int>&b)
{
n=nn, bits=s;
id=0,node=0;
dfs(0);
vector<int>ans;
for(int i=0;i<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;
}
