#include <stdlib.h>
#include <string.h>
#include "bits/stdc++.h"
#include "floppy.h"
namespace {
constexpr int inf = int(1E9) + 5;
};
void read_array(int subtask_id, const std::vector<int> &v) {
// std::string bits = "001100";
// save_to_floppy(bits);
int N = int(v.size());
std::string s;
std::vector<int> stk;
for (int i = 0; i < N; ++i) {
while (!stk.empty() && v[stk.back()] < v[i]) {
s += '0';
stk.pop_back();
}
s += '1';
stk.emplace_back(i);
}
save_to_floppy(s);
}
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
// std::vector<int> answers = {0, 0, 0, 0, 1, 2, 2, 2, 2, 3};
// return answers;
int Q = int(a.size());
std::vector<int> ans(Q);
const int LG = std::__lg(N);
std::vector<int> stk;
std::vector<std::vector<int>> prv(LG + 1, std::vector<int>(N));
int p = 0;
for (int i = 0; i < N; ++i) {
while (bits[p] != '1') {
p++;
stk.pop_back();
}
prv[0][i] = stk.empty() ? -1 : stk.back();
stk.emplace_back(i);
p++;
}
for (int i = 1; i <= LG; ++i) {
for (int j = 0; j < N; ++j) {
if (prv[i - 1][j] == -1) {
prv[i][j] = -1;
} else {
prv[i][j] = prv[i - 1][prv[i - 1][j]];
}
}
}
for (int i = 0; i < Q; ++i) {
int x = b[i];
for (int j = LG; j >= 0; --j) {
if (prv[j][x] >= a[i]) {
x = prv[j][x];
}
}
ans[i] = x;
}
return ans;
}
