#pragma GCC optimize("O3, unroll-loops, Ofast")
#include <stdlib.h>
#include <string.h>
#include<bits/stdc++.h>
#include "floppy.h"
#define pii pair<int,int>
using namespace std;
int B = 0;
int INF = numeric_limits<int>::max()/2;
struct SegmentTree{
vector<pii> S;
int len = 1;
SegmentTree(vector<int>arr){
int n = arr.size();
while(len < n) len <<= 1;
S.resize(2*len, {-INF,-1});
for(int i = 0; i < n;i++){
S[i+len] = {arr[i],i};
}
for(int i = len-1; i > 0; i--){
S[i] = max(S[i*2],S[i*2+1]);
}
}
pii query(int ql, int qr, int l = 0, int r = -2, int i = 1){
if(r == -2) r = len;
if(ql <= l && r <= qr) return S[i];
if(r <= ql || qr <= l) return {-INF,-1};
int mid = (l+r)/2;
return max(query(ql,qr,l,mid,i*2),query(ql,qr,mid,r,i*2+1));
}
};
void build(int l, int r, SegmentTree& seg, string& bits){
if(l == r){
bits += "00";
return;
}
pii res = seg.query(l,r+1);
if(res.second == l){
bits += "01";
build(l+1, r, seg, bits);
}else if(res.second == r){
bits += "10";
build(l, r-1, seg, bits);
}else{
bits += "11";
build(l, res.second-1, seg, bits);
build(res.second+1, r, seg, bits);
}
}
void read_array(int subtask_id, const std::vector<int> &arr) {
vector<int >v = arr;
int n =v.size();
string bits = "";
SegmentTree seg(v);
build(0,n-1,seg,bits);
cerr << bits<<endl;
save_to_floppy(bits);
}
int counter = 0;
struct Node{
int v;
int l = -1, r = -1;
int sz = 1;
int lsz = 0, rsz= 0;
};
vector<Node> cart;
void reconstruct(vector<Node>& adj, string& bits){
bool b1 = bits[counter] == '1';
bool b2 = bits[counter+1] == '1';
counter += 2;
int v = cart.size();
cart.push_back(Node{});
if(b1){
cart[v].l = cart.size();
reconstruct(adj,bits);
cart[v].sz += cart[cart[v].l].sz;
cart[v].lsz = cart[cart[v].l].sz;
}
if(b2){
cart[v].r = cart.size();
reconstruct(adj,bits);
cart[v].sz += cart[cart[v].r].sz;
cart[v].rsz = cart[cart[v].r].sz;
}
}
void buildInd(int v, int l, int r){
cart[v].v = cart[v].lsz + l;
if(cart[v].l != -1){
buildInd(cart[v].l, l, cart[v].v-1);
}
if(cart[v].r != -1){
buildInd(cart[v].r,cart[v].v+1, r);
}
}
int search(int v, int l, int r){
if(l <= cart[v].v && cart[v].v <= r){
return cart[v].v;
}
if(cart[v].v < l){
return search(cart[v].r, l, r);
}else{
return search(cart[v].l, l, r);
}
}
std::vector<int> solve_queries(int subtask_id, int N, const std::string &input, const std::vector<int> &a, const std::vector<int> &b) {
int n = N;
string bits = input;
B = ceil(log2(n));
int q = a.size();
vector<Node> adj;
reconstruct(adj,bits);
buildInd(0,0,n-1);
vector<int> answers(q);
for(int i = 0; i < q; i++){
int l, r;
l = a[i];
r = b[i];
if(l == r){
answers[i] = l;
continue;
}
answers[i] = search(0,l,r);
}
return answers;
}
