#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
#define name "aaaaaa"
#define endl "\n"
#define fi first
#define se second
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdb = pair<db, db>;
using ppii = pair<ll, pii>;
using ull = unsigned long long;
using vvi = vector<vector<int>>;
void read_array(int subtask_id, const vector<int> &v){
string s;
vector<int> st;
for(int i = 0; i < v.size(); i++){
while(!st.empty()){
if(v[st.back()] < v[i]){
st.pop_back();
s += '0';
}else{
break;
}
}
s += '1';
st.push_back(i);
}
save_to_floppy(s);
}
vector<int> solve_queries(int subtask_id, int n, const string& bits, const vector<int>& a, const vector<int>& b){
vector<vector<int>> lift(n, vector<int>(20, -1));
vector<int> st;
int id = -1;
for(char c : bits){
if(c == '0'){
st.pop_back();
}else{
id++;
if(!st.empty()) lift[id][0] = st.back();
st.push_back(id);
}
}
for(int i = 1; i < 20; i++){
for(int j = 0; j < n; j++){
if(lift[j][i - 1] != -1) lift[j][i] = lift[lift[j][i - 1]][i - 1];
}
}
vector<int> ans(a.size());
for(int i = 0; i < a.size(); i++){
int l = a[i], r = b[i];
for(int j = 19; j >= 0; j--){
if(lift[r][j] >= l) r = lift[r][j];
}
ans[i] = r;
}
return ans;
}
