#include<bits/stdc++.h>
#include "floppy.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
//#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r) {
return uniform_int_distribution<int>(l,r)(rng);
}
int st[100005];
int dr[100005];
void read_array(int subtask_id, const vector<int> &v) {
int i,t;
string bits;
t=0;
for (i=0; i<v.size(); i++) {
if (t==0 || v[i]<=v[st[t]]) {
t++;
st[t]=i;
bits+="1";
} else {
while (t>0 && v[i]>v[st[t]]) {
bits+="0";
t--;
}
t++;
st[t]=i;
bits+="1";
}
}
while (t>0) {
bits+="0";
t--;
}
save_to_floppy(bits);
}
vector<int> solve_queries(int subtask_id, int N,
const string &bits,
const vector<int> &a, const vector<int> &b) {
vector<int> sol;
int i,j,t,cnt,l,r;
t=0;
cnt=0;
for (i=0; i<bits.size(); i++) {
if (bits[i]=='1') {
t++;
st[t]=cnt;
cnt++;
} else {
dr[st[t]]=cnt;
t--;
}
}
sol.clear();
for (i=0; i<a.size(); i++) {
l=a[i];
r=b[i];
for (j=l; j<=r; j++) {
if (dr[j]>r) {
sol.push_back(j);
break;
}
}
}
return sol;
}
