#include<bits/stdc++.h>
#include "floppy.h"

using namespace std;

template<class T, class F>
struct sparse_table{
    int n;
    vector<vector<T>> data;
    F TT;
    T T_id;
    sparse_table(){ }
    // O(n log n)
    sparse_table(const vector<T> &a, F TT, T T_id): n((int)a.size()), TT(TT), T_id(T_id), data({a}){
        for(auto p = 1, i = 1; p << 1 <= n; p <<= 1, ++ i){
            data.emplace_back(n - (p << 1) + 1);
            for(auto j = 0; j < (int)data[i].size(); ++ j) data[i][j] = TT(data[i - 1][j], data[i - 1][j + p]);
        }
    }
    // O(1)
    T query(int l, int r) const{
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return T_id;
        int d = __lg(r - l);
        return TT(data[d][l], data[d][r - (1 << d)]);
    }
};

pair<int, int> op(pair<int, int> a, pair<int, int> b) { return max(a, b); }

void read_array(int subtask_id, const std::vector<int> &v) {
    int n = (int)(v.size());
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i) a[i] = {v[i], i};
    sparse_table st(a, op, pair{0, 0});

    vector<vector<int>> G(n);
    auto dfs = [&](auto self, int l, int r) -> int {
        if (l == r) return ~l;
        int pos = st.query(l, r).second;
        G[pos].emplace_back(self(self, l, pos));
        G[pos].emplace_back(self(self, pos + 1, r));
        return pos;
    };
    int root = dfs(dfs, 0, n);
    auto dfs2 = [&](auto self, int v) -> pair<int, string> {
        vector<pair<int, string>> vec;
        for (int u : G[v]) {
            if (u < 0) vec.emplace_back(u, "");
            else vec.push_back(self(self, u));
        }
        sort(vec.rbegin(), vec.rend());
        if (vec[0].second.empty() and vec[1].second.empty()) return {vec[0].first, "01"};
        if (vec[0].second.empty()) return {vec[0].first, "0" + vec[1].second + "1"};
        if (vec[1].second.empty()) return {vec[0].first, vec[0].second + "01"};
        return {vec[0].first, vec[0].second + "0" + vec[1].second + "1"};
    };
    save_to_floppy(dfs2(dfs2, root).second);
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    int n = (int)(bits.size()) / 2;
    vector<pair<int, int>> aa(n);
    for (int i = 0; i < n; ++i) aa[i].second = i;
    // cerr << bits << endl;
    auto dfs = [&](auto self, int posl, int posr, int l, int r, int l1, int r1) -> void {
        // cout << "dfs: " << posl << " " << posr << " " << l << " " << r << " " << l1 << " " << r1 << endl;
        int len = posr - posl + 1, sum = 0, pos = -1;
        if (len == 2) {
            aa[l].first = r1;
            return;
        }
        for (int i = posr; i >= posl; --i) {
            sum += (bits[i] == '1' ? 1 : -1);
            if (sum == 0) {
                pos = i;
                break;
            }
        }
        assert(pos != -1);
        if (pos == posl) {
            aa[l].first = r1;
            self(self, posl + 1, posr - 1, l + 1, r, l1, r1 - 1);
        }
        else if (pos == posr - 1) {
            aa[r].first = r1;
            self(self, posl, posr - 2, l, r - 1, l1, r1 - 1);
        }
        else {
            int inter = l + pos / 2;
            aa[inter].first = r1;
            self(self, posl, posl + pos - 2, l, inter - 1, l1, l1 + pos / 2 - 1);
            self(self, posl + pos, posr - 1, inter + 1, r, l1 + pos / 2, r1 - 1);
        }
    };
    dfs(dfs, 0, 2 * n - 1, 0, n - 1, 0, n - 1);
    sparse_table st(aa, op, pair{0, 0});
    vector<int> answers((int)(a.size()));
    for (int i = 0; i < (int)(a.size()); ++i) {
        answers[i] = st.query(a[i], b[i] + 1).second;
    }
    return answers;
}