#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
const int M = 40001, lg = 16;
int maxx[M][lg],a[M],par[M][lg],ch[M][2],id[M],nd[M],ind[M],dep[M],t;
string s;
int get(int l,int r)
{
int b=31-__builtin_clz(r-l);
if (a[maxx[l][b]]>a[maxx[r-(1<<b)][b]])
return maxx[l][b];
return maxx[r-(1<<b)][b];
}
void f(int l,int r)
{
int id=get(l,r);
if (id!=l) s+='1',f(l,id);
else s+='0';
if (id!=r-1) s+='1',f(id+1,r);
else s+='0';
}
void read_array(int subtask_id, const vector<int> &A)
{
int n=A.size();
for (int i=0;i<n;i++) a[i]=A[i],maxx[i][0]=i;
for (int p=1;p<lg;p++)
for (int i=0;i+(1<<p)<=n;i++)
{
maxx[i][p]=maxx[i][p-1];
if (a[maxx[i][p-1]]<a[maxx[i+(1<<p-1)][p-1]])
maxx[i][p]=maxx[i+(1<<p-1)][p-1];
}
f(0,n);
save_to_floppy(s);
}
void dfs(int u)
{
if (ch[u][0])
dfs(ch[u][0]);
ind[u]=t,nd[t++]=u;
if (ch[u][1])
dfs(ch[u][1]);
}
int lca(int u,int v)
{
if (dep[u]>dep[v]) swap(u,v);
for (int p=lg-1;p>=0;p--)
if (dep[v]-dep[u]>=(1<<p))
v=par[v][p];
if (u==v) return u;
for (int p=lg-1;p>=0;p--)
if (par[u][p]!=par[v][p])
u=par[u][p],v=par[v][p];
return par[u][0];
}
vector<int> solve_queries(int subtask_id, int n,
const string &s,
const vector<int> &a, const vector<int> &b) {
vector<int> ans;
int r=1,nx=2;
for (int i=0;i<2*n;i++)
{
while (id[r]==2)
r=par[r][0];
if (s[i]=='1')
ch[r][id[r]++]=nx,par[nx][0]=r,dep[nx]=dep[r]+1,r=nx++;
else
id[r]++;
}
dfs(1);
for (int p=1;p<lg;p++)
for (int i=0;i<n;i++)
par[i][p]=par[par[i][p-1]][p-1];
for (int i=0;i<a.size();i++)
ans.push_back(ind[lca(nd[a[i]],nd[b[i]])]);
return ans;
}
