#include <algorithm>
#include <iostream>
#include "floppy.h"
#include <vector>
#include <string>
#include <stack>
using namespace std;
void read_array(int subtask_id, const vector <int> &v) {
string bits = "\0";
stack <int> st;
for (int i = 0; i < v.size(); ++i) {
while (!st.empty() && v[st.top()] < v[i]) {
bits += "0";
st.pop();
}
bits += "1";
st.push(i);
}
save_to_floppy(bits);
}
const int N = 8e4 + 10;
vector <int> q[N];
int ans[N];
bool cmp(const int &x, const int &y) {
return x > y;
}
vector <int> solve_queries (int subtask_id, int n, const string &bits, const vector <int> &l, const vector <int> &r) {
for (int i = 0; i < r.size(); ++i) {
q[r[i]].push_back(i);
}
int cnt = 0;
vector <int> cur;
for (int i = 0; i < bits.size(); ++i) {
if (bits[i] == 1) {
cur.push_back(cnt);
for (int z: q[cnt]) {
auto it = lower_bound(cur.begin(), cur.end(), l[z], cmp);
ans[z] = *it;
}
} else cur.pop_back();
}
vector <int> res;
for (int i = 0; i < l.size(); ++i) {
res.push_back(ans[i]);
}
return res;
}
