#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];
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]) {
int L = 0, R = (int)cur.size() - 1, curval = R;
while (L <= R) {
int mid = (L + R) >> 1;
if (cur[mid] >= l[z]) {
curval = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
ans[z] = cur[curval];
}
++cnt;
} else cur.pop_back();
}
vector <int> res;
for (int i = 0; i < l.size(); ++i) {
res.push_back(ans[i]);
}
return res;
}
