#include <stdlib.h>
#include <string.h>
#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
void read_array(int subtask_id, const vector<int> &arr) {
string bits;
stack<int>st;
for(int i = 0;i<sz(arr);i++){
while(!st.empty() and st.top() < arr[i]){
st.pop();
bits += '0';
}
st.push(arr[i]);
bits += '1';
}
save_to_floppy(bits);
}
struct SEGT{
vector < pair<int,int> > t;// value index
int tree_size;
const pair<int,int> identity_element = {0,0};
pair<int,int> merge(pair<int,int> x , pair<int,int> y){
return max(x,y);
}
void init(int x){
tree_size = x+3;
t.assign(2*tree_size , identity_element);
}
void modify(int p, pair<int,int> value) { // set value at position p
for (t[p += tree_size] = value; p > 1; p >>= 1){
t[p>>1] = merge(t[p] , t[p^1]);
}
}
int query(int l, int r) { // sum on interval [l, r]
pair<int,int> res = identity_element;
for (r+=1 , l += tree_size, r += tree_size; l < r; l >>= 1, r >>= 1) {
if (l&1) res = merge(res , t[l++]);
if (r&1) res = merge(res , t[--r]);
}
return res.second;
}
};
vector<int> solve_queries(int subtask_id, int n,
const string &bits,const vector<int> &a, const vector<int> &b) {
vector<int>tree[n+1];
stack<int>st;
int sayac = 0 , arr[n+1];
for(int i = 1;i<=n;i++){
while(bits[sayac] == '0'){
st.pop();
sayac++;
}
if(!st.empty())
tree[st.top()].push_back(i);
else
tree[0].push_back(i);
st.push(i);
sayac++;
}
sayac = 1;
function<void(int)> dfs = [&](int node){
for(auto itr : tree[node])
dfs(itr);
arr[node] = sayac++;
};
dfs(0);
SEGT segt;
segt.init(n+1);
for(int i = 1;i<=n;i++){
segt.modify(i , {arr[i] , i});
}
vector<int>answers;
for(int i = 0;i<sz(a);i++){
answers.push_back(segt.query(a[i]+1 , b[i]+1)-1);
}
return answers;
}
