#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
namespace p1
{
vector <int> arr;
vector <vector <int>> st;
int n;
void build_st ()
{
st.push_back (vector <int> (n, 0));
for (int i = 0; i < n; i ++)
st[0][i] = i;
for (int j = 1; (1 << j) <= n; j ++)
{
st.push_back (vector <int> (n, 0));
for (int i = 0; i < n; i ++)
{
st[j][i] = st[j - 1][i];
if (i + (1 << j - 1) < n and arr[st[j - 1][i + (1 << j - 1)]] > arr[st[j][i]])
st[j][i] = st[j - 1][i + (1 << j - 1)];
}
}
/*
for (auto i: st)
{
for (auto j: i) cout << j << ' ';
cout << '\n';
}
*/
}
int rmq (int l, int r)
{
int lg = 0;
while ((1 << lg) + l <= r + 1) lg ++;
lg --;
int cx = st[lg][l], cy = st[lg][r - (1 << lg) + 1];
if (arr[cx] > arr[cy]) return cx;
else return cy;
}
string ans;
void dfs_range (int l, int r)
{
if (l > r) return;
int pos = rmq (l, r);
//cout << l << ' ' << r << ' ' << pos << endl;
int lc = true, rc = true;
if (pos == l) lc = false;
if (pos == r) rc = false;
ans += char (lc + '0');
ans += char (rc + '0');
dfs_range (l, pos - 1);
dfs_range (pos + 1, r);
return;
}
void solve (vector <int> v)
{
arr = v;
n = arr.size ();
build_st ();
dfs_range (0, n - 1);
save_to_floppy (ans);
return;
}
}
namespace p2 {
struct Node {
Node* left;
Node* right;
int inIdx;
Node(): left(nullptr), right(nullptr), inIdx(-1) {}
};
int decodePos = 0;
Node* decodeTree(const string &bits) {
int hasLeft = bits[decodePos] - '0';
int hasRight = bits[decodePos + 1] - '0';
decodePos += 2;
Node* node = new Node();
if (hasLeft)
node->left = decodeTree(bits);
if (hasRight)
node->right = decodeTree(bits);
return node;
}
void inorderTraversal(Node* node, vector<Node*> &inorderNodes) {
if (!node) return;
inorderTraversal(node->left, inorderNodes);
node->inIdx = inorderNodes.size();
inorderNodes.push_back(node);
inorderTraversal(node->right, inorderNodes);
}
void eulerTour(Node* node, int depth, vector<Node*> &euler, vector<int> &eulerDepth, vector<int> &firstOccurrence) {
if (!node) return;
if (firstOccurrence[node->inIdx] == -1)
firstOccurrence[node->inIdx] = euler.size();
euler.push_back(node);
eulerDepth.push_back(depth);
if (node->left) {
eulerTour(node->left, depth + 1, euler, eulerDepth, firstOccurrence);
euler.push_back(node);
eulerDepth.push_back(depth);
}
if (node->right) {
eulerTour(node->right, depth + 1, euler, eulerDepth, firstOccurrence);
euler.push_back(node);
eulerDepth.push_back(depth);
}
}
vector<vector<int>> buildSparseTable(const vector<int> &eulerDepth) {
int m = eulerDepth.size();
int K = floor(log2(m)) + 1;
vector<vector<int>> st(K, vector<int>(m));
for (int i = 0; i < m; i++) {
st[0][i] = i;
}
for (int k = 1; (1 << k) <= m; k++) {
for (int i = 0; i + (1 << k) - 1 < m; i++) {
int idx1 = st[k - 1][i];
int idx2 = st[k - 1][i + (1 << (k - 1))];
st[k][i] = (eulerDepth[idx1] < eulerDepth[idx2]) ? idx1 : idx2;
}
}
return st;
}
int querySparseTable(const vector<int> &eulerDepth, const vector<vector<int>> &st, int L, int R) {
int len = R - L + 1;
int k = floor(log2(len));
int idx1 = st[k][L];
int idx2 = st[k][R - (1 << k) + 1];
return (eulerDepth[idx1] < eulerDepth[idx2]) ? idx1 : idx2;
}
vector<int> solve(int N, string bits, vector<int> a, vector<int> b) {
decodePos = 0;
Node* root = decodeTree(bits);
vector<Node*> inorderNodes;
inorderTraversal(root, inorderNodes);
vector<Node*> euler;
vector<int> eulerDepth;
vector<int> firstOccurrence(N, -1);
eulerTour(root, 0, euler, eulerDepth, firstOccurrence);
vector<vector<int>> st = buildSparseTable(eulerDepth);
int Q = a.size();
vector<int> ans(Q, 0);
for (int i = 0; i < Q; i++) {
int idxA = a[i];
int idxB = b[i];
if (idxA > idxB) swap(idxA, idxB);
int firstA = firstOccurrence[idxA];
int firstB = firstOccurrence[idxB];
if (firstA > firstB) swap(firstA, firstB);
int pos = querySparseTable(eulerDepth, st, firstA, firstB);
Node* lca = euler[pos];
ans[i] = lca->inIdx;
}
return ans;
}
}
void read_array(int subtask_id, const vector<int>& v)
{
p1::solve (v);
return;
}
vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int>& a, const vector<int>& b)
{
return p2::solve (N, bits, a, b);
}
