#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
int n, le[40005], ri[40005], par[16][40005], lc[40005], rc[40005];
vector<int> G[40005];
string res, s;
void findTour(int u){
res += '0' + (lc[u] != -1);
res += '0' + (rc[u] != -1);
for(int c: G[u]) findTour(c);
}
void read_array(int subtask_id, const std::vector<int> &v) {
n = v.size();
vector<int> S;
for(int i=0;i<n;i++){
lc[i] = rc[i] = -1;
while(!S.empty()){
int x = S.back();
if(v[x] < v[i]) S.pop_back();
else break;
}
if(S.empty()){
le[i] = -1;
}else le[i] = S.back();
S.push_back(i);
}
S.clear();
for(int i=n-1;i>=0;i--){
while(!S.empty()){
int x = S.back();
if(v[x] < v[i]) S.pop_back();
else break;
}
if(S.empty()){
ri[i] = -1;
}else ri[i] = S.back();
S.push_back(i);
}
int root = 0;
for(int i=0;i<n;i++){
int p = -1;
bool isLeft = true;
if(le[i] == -1) {
p = ri[i];
isLeft = 1;
}else if(ri[i] == -1) {
p = le[i];
isLeft = 0;
}else{
if(v[le[i]] < v[ri[i]]) {
p = le[i];
isLeft = 0;
}else {
p = ri[i];
isLeft = 1;
}
}
if(p == -1) {
root = i;
continue;
}
if(isLeft) lc[p] = i;
else rc[p] = i;
G[p].push_back(i);
}
// for(int i=0;i<n;i++) {
//// cout << idn[i] << " = " << i << endl;
// for(int c: G[i]){
// cout << i << " -> " << c << endl;
// }
// }
findTour(root);
save_to_floppy(res);
}
int cu, idn[40005], cornode[40005], depth[40005];
pair<int,int> getTour(int sp, int ss){
// cout << sp << ' ' << ss << endl;
// cout << u << endl;
// cout << u << " (" << le[u] << ", " << ri[u] << ")" << endl;
int u = cu++;
idn[u] = sp;
int ssn = ss + 2;
pair<int,int> rr = {idn[u], ssn};
if(s[ss] == '1'){
// cout << u << " --> " << cu << endl;
G[u].push_back(cu);
depth[cu] = depth[u] + 1;
par[0][cu] = u;
rr = getTour(sp, ssn);
idn[u] = rr.first;
ssn = rr.second;
}
if(s[ss+1] == '1'){
// cout << u << " --> " << cu << endl;
G[u].push_back(cu);
depth[cu] = depth[u] + 1;
par[0][cu] = u;
rr = getTour(idn[u] + 1, ssn);
}else rr.first++;
// cout << u << ' ' << s[ss] << s[ss+1] << ' ' << idn[u] << endl;
return rr;
}
int LCA(int u, int v){
if(depth[u] > depth[v]) swap(u, v);
int l = depth[v] - depth[u];
for(int i=0;i<16;i++){
if(l & (1 << i)) v = par[i][v];
}
if(u == v) return u;
for(int i=15;i>=0;i--){
if(par[i][u] != par[i][v]){
u = par[i][u];
v = par[i][v];
}
}
return par[0][u];
}
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
// cout << bits << endl;
for(int i=0;i<N;i++) G[i].clear();
s = bits;
cu = 0;
getTour(0, 0);
for(int i=0;i<N;i++){
for(int x=1;x<16;x++){
par[x][i] = par[x-1][par[x-1][i]];
}
}
// for(int i=0;i<N;i++) {
//// cout << idn[i] << " = " << i << endl;
// for(int c: G[i]){
// cout << i << " --> " << c << endl;
// }
// }
for(int i=0;i<N;i++) {
// cout << idn[i] << " = " << i << endl;
// cout << "! " << i << ' ' << idn[i] << endl;
cornode[idn[i]] = i;
}
vector<int> answers;
for(int i=0;i<a.size();i++){
int u = cornode[a[i]], v = cornode[b[i]];
// cout << "? " << a[i] << ' ' << b[i] << ' ' << u << ' ' << v << ' ' << LCA(u, v) << ' ' << idn[LCA(u, v)] << endl;
answers.push_back(idn[LCA(u, v)]);
}
return answers;
}
