#include <bits/stdc++.h>
using namespace std;
#include "floppy.h"
vector<bool> construct(const vector<int>& v) {
vector<bool> construction;
stack<int> right_path; // save indizes
right_path.push(0);
for (int i = 1; i < v.size(); i++) {
while (!right_path.empty() && v[right_path.top()] < v[i]) {
right_path.pop();
construction.push_back(0);
}
right_path.push(i);
construction.push_back(1);
}
return construction;
}
tuple<int, vector<int>, vector<int>, vector<int>> reconstruct(int n, vector<bool>& construction) {
int root = 0;
vector<int> left(n, -1);
vector<int> right(n, -1);
vector<int> par(n, -1);
stack<int> right_path;
right_path.push(-1);
right_path.push(0);
int construction_idx = 0;
for (int i = 1; i < n; i++) {
int count = 0;
while (construction[construction_idx] == 0) {
construction_idx++;
count++;
}
int to_replace = -1;
for (int j = 0; j < count; j++) {
to_replace = right_path.top();
right_path.pop();
}
int p = right_path.top();
if (p != -1) right[p] = i;
else root = i;
par[i] = p;
if (to_replace != -1) par[to_replace] = i;
left[i] = to_replace;
right_path.push(i);
construction_idx++;
}
return {root, left, right, par};
}
void read_array(int subtask_id, const std::vector<int> &v) {
vector<bool> construction = construct(v);
string bits;
for (auto e : construction) bits.append(e ? "1" : "0");
save_to_floppy(bits);
}
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
vector<bool> construction(N);
for (int i = 0; i < N; i++) construction[i] = bits[i] == '1';
auto [root, left, right, par] = reconstruct(N, construction);
vector<vector<int>> jump(30, vector<int>(N));
jump[0] = par;
jump[0][root] = root;
for (int i = 1; i < 30; i++) {
for (int u = 0; u < N; u++) {
jump[i][u] = jump[i-1][jump[i-1][u]];
}
}
vector<int> depth(N);
function<void(int,int)> dfs = [&](int u, int dep) {
if (u == -1) return;
depth[u] = dep;
dfs(left[u], dep+1);
dfs(right[u], dep+1);
};
dfs(root, 0);
function<int(int,int)> lift = [&](int u, int h) {
for (int i = 29; i >= 0; i--) {
if (h & (1 << i)) u = jump[i][u];
}
return u;
};
function<int(int,int)> lca = [&](int u, int v) {
if (depth[u] > depth[v]) swap(u,v);
v = lift(v, depth[v]-depth[u]);
assert (depth[u] == depth[v]);
if (u == v) return u;
for (int i = 29; i >= 0; i--) {
if (jump[i][u] != jump[i][v]) {
u = jump[i][u];
v = jump[i][v];
}
}
return jump[0][u];
};
vector<int> ans(a.size());
for (int i = 0; i < a.size(); i++) {
ans[i] = lca(a[i], b[i]);
}
return ans;
}
