#include<bits/stdc++.h>
#include "floppy.h"
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
void dfs(int x, vector<int> & L, vector<int>& R, string& bits) {
if (x == -1) return;
bits += (L[x] != -1) + '0';
bits += (R[x] != -1) + '0';
dfs(L[x], L, R, bits);
dfs(R[x], L, R, bits);
}
void read_array(int subtask_id, const vector<int> &v) {
int n = v.size(), x;
vector<vector<int>> adj(n, vector<int>());
vector<int> L(n, -1), R(n, -1);
stack<int> st;
string bits = "";
for (int i = 0; i < n; i++) {
while (st.size() && v[st.top()] < v[i]) {
int j = st.top(); st.pop();
if (st.empty() || v[st.top()] > v[i]) L[i] = j;
else R[st.top()] = j;
}
st.emplace(i);
}
while (st.size()) {
x = st.top(); st.pop();
if (st.size()) R[st.top()] = x;
}
dfs(x, L, R, bits);
save_to_floppy(bits);
}
const int B = 1 << 16;
int t, cur;
pair<int, int> seg[B * 2];
void find(const string& bits, int v) {
int tmp = t++;
if (bits[tmp * 2] == '1') find(bits, v - 1);
seg[B + cur] = {v, cur};
cur++;
if (bits[tmp * 2 + 1] == '1') find(bits, v - 1);
}
int Max(int l, int r) {
l += B; r += B;
pair<int, int> ret = {0, 0};
while (l <= r) {
if (l & 1) ret = max(ret, seg[l++]);
if (!(r & 1)) ret = max(ret, seg[r--]);
l >>= 1;r >>= 1;
}
return ret.second;
}
vector<int> solve_queries(int subtask_id, int N,
const string &bits,
const vector<int> &a, const std::vector<int> &b) {
find(bits, N);
vector<int> ans;
for (int i = B - 1; i; i--) seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
for (int i = 0; i < a.size(); i++) ans.emplace_back(Max(a[i], b[i]));
return ans;
}
