#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
const int nx=4e4+5, kx=16;
int l[nx], r[nx], pa[nx][kx], lvl[nx];
void dfs(int u, int p)
{
pa[u][0]=p;
lvl[u]=lvl[p]+1;
for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
if (l[u]!=-1) dfs(l[u], u);
if (r[u]!=-1) dfs(r[u], u);
}
int lca(int u, int v)
{
if (lvl[u]>lvl[v]) swap(u, v);
for (int i=kx-1; i>=0; i--) if (lvl[u]<=lvl[pa[v][i]]) v=pa[v][i];
if (u==v) return u;
for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
return pa[u][0];
}
void read_array(int subtask_id, const std::vector<int> &v) {
string str;
stack<int> s;
for (int i=0; i<v.size(); i++)
{
while (!s.empty()&&v[s.top()]<v[i]) s.pop(), str.push_back('1');
s.push(i);
str.push_back('0');
}
save_to_floppy(str);
}
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
stack<int> s;
int idx=0, rt=-1, cur=0;
for (int i=0; i<N; i++) l[i]=r[i]=-1;
//cout<<"bits "<<bits<<'\n';
while (cur<bits.size())
{
//cout<<"here "<<cur<<' '<<bits[cur]<<' '<<bits.size()<<'\n';
while (bits[cur]=='1') l[idx]=s.top(), cur++, s.pop();
//cout<<"after\n";
if (!s.empty()) r[s.top()]=idx;
else rt=idx;
cur++;
s.push(idx++);
}
//for (int i=0; i<N;i ++) cout<<i<<' '<<l[i]<<' '<<r[i]<<'\n';
dfs(rt, rt);
vector<int> res;
for (int i=0; i<a.size(); i++) res.push_back(lca(a[i], b[i])); //cout<<"val "<<a[i]<<' '<<b[i]<<' '<<lca(a[i], b[i])<<'\n';
return res;
}
/*
g++ grader.cpp floppy.cpp -o a
*/
