#include "bits/stdc++.h"
#include "floppy.h"
using namespace std;
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vd = vector<db>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vpl = vector<pl>;
void read_array(int subtask_id, const std::vector<int> &v) {
std::string bits = "";
stack<int> st;
int N = sz(v);
FOR(i, 0, N){
while(!st.empty() && v[st.top()] <= v[i]){
st.pop();
bits += "0";
}
st.push(i);
bits += "1";
}
assert(sz(bits) <= 2 * N);
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) {
stack<int> st;
int idx = 0;
vector<vi> lift(20, vi(N, -1));
FOR(i, 0, sz(bits)){
if(bits[i] == '0') st.pop();
else{
lift[0][idx] = (st.empty() ? -1 : st.top());
st.push(idx++);
// cout << lift[0][idx-1] << " \n"[i == N];
}
}
for(int i = 1; (1 << i) <= N; ++i){
for(int j = 0; j < N; ++j){
if(lift[i-1][j] == -1) lift[i][j] = -1;
else lift[i][j] = lift[i-1][lift[i-1][j]];
}
}
vi answers;
int M = sz(a);
FOR(i, 0, M){
int l = a[i], r = b[i];
ROF(i, 20, 0){
if(lift[i][r] >= l) r = lift[i][r];
}
answers.pb(r);
}
return answers;
}
