#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
#define NMAX 100000
#define MMAX 100000
int leftc[NMAX], rightc[NMAX];
int par[18][NMAX], depth[NMAX];
int timer = 0;
void dfs_1(int u, const string &bits)
{
if(bits[2*u] == '1')
{
int new_node = ++timer;
par[0][new_node] = u;
leftc[u] = new_node;
depth[new_node] = depth[u]+1;
dfs_1(new_node, bits);
}
if(bits[2*u+1] == '1')
{
int new_node = ++timer;
par[0][new_node] = u;
rightc[u] = new_node;
depth[new_node] = depth[u]+1;
dfs_1(new_node, bits);
}
}
int jump(int a, int l)
{
for(int i = 0; i < 18; i++)
if((l&(1<<i)) != 0)
a = par[i][a];
return a;
}
int lca(int a, int b)
{
if(depth[a] < depth[b])
swap(a, b);
a = jump(a, depth[a]-depth[b]);
if(a == b)
return a;
for(int i = 17; i >= 0; i--)
if(par[i][a] != par[i][b])
a = par[i][a],
b = par[i][b];
return par[0][a];
}
int trans[NMAX], inv_trans[NMAX];
int code = 0;
void dfs_2(int u)
{
if(leftc[u] != -1)
dfs_2(leftc[u]);
trans[u] = code;
inv_trans[code] = u;
code++;
if(rightc[u] != -1)
dfs_2(rightc[u]);
}
vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b)
{
for(int i = 0; i <= n; i++)
{
leftc[i] = -1;
rightc[i] = -1;
par[0][i] = -1;
}
dfs_1(0, bits);
for(int i = 1; i <= 17; i++)
for(int j = 0; j < n; j++)
par[i][j] = par[i-1][par[i-1][j]];
dfs_2(0);
vector<int> answers;
for(int i = 0; i < a.size(); i++)
{
answers.push_back(trans[lca(inv_trans[a[i]], inv_trans[b[i]])]);
}
return answers;
}
void read_array(int subtask_id, const vector<int> &v)
{
int n = v.size();
int rc[n], lc[n], p[n];
for(int i = 0; i < n; i++)
{
rc[i] = -1;
lc[i] = -1;
p[i] = -1;
}
int root = 0;
for(int i = 1; i < n; i++)
{
int last_val = i-1;
while(last_val != -1)
{
if(-v[last_val] < -v[i])
{
lc[i] = rc[last_val];
rc[last_val] = i;
p[i] = last_val;
p[lc[i]] = i;
break;
}
last_val = p[last_val];
}
if(last_val == -1)
{
lc[i] = root;
p[root] = i;
root = i;
}
}
string bits = "";
stack<int> s;
s.push(root);
while(!s.empty())
{
int nw = s.top();
s.pop();
string bruh = "00";
if(rc[nw] != -1)
{
bruh[1] = '1';
s.push(rc[nw]);
}
if(lc[nw] != -1)
{
bruh[0] = '1';
s.push(lc[nw]);
}
bits+=bruh;
}
save_to_floppy(bits);
}
