#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
struct Segtree {
vector<int> seg;
int n;
void build(int n, int l, int r, vector<int> &init){
if(l == r){
seg[n] = init[l-1];
return;
}
int m = (l+r)/2;
build(2*n, l, m, init);
build(2*n+1, m+1, r, init);
seg[n] = max(seg[2*n], seg[2*n+1]);
}
Segtree(vector<int> init) {
n = init.size();
seg.resize(4*n);
build(1, 1, n, init);
}
int __query(int n, int l, int r, int left, int right){
if(l > right || r < left)
return -1;
if(left <= l && r <= right)
return seg[n];
int m = (l+r)/2;
return max(__query(2*n, l, m, left, right), __query(2*n+1, m+1, r, left, right));
}
int query(int left, int right){
return __query(1, 1, n, left, right);
}
};
void read_array(int subtask_id, const vector<int> &v){
int n = v.size();
vector<pair<int, int>> comp(n);
for(int i=0;i<n;i++){
comp[i] = {v[i], i};
}
sort(comp.begin(), comp.end());
vector<int> res(n);
for(int i=0;i<n;i++){
res[comp[i].second] = i;
}
int l = 31 - __builtin_clz(n);
string s;
for(int i=0;i<n;i++){
for(int j=1<<l;j>0;j>>=1){
if(res[i] & j)
s.push_back('1');
else
s.push_back('0');
}
}
save_to_floppy(s);
}
vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b){
int m = a.size();
vector<int> res(m);
int l = 32 - __builtin_clz(n);
vector<int> arr(n);
for(int i=0;i<n;i++){
for(int j=0;j<l;j++){
if(bits[i*l+j] == '1')
arr[i] += (1<<(l-j-1));
}
}
Segtree seg(arr);
vector<int> rev(n);
for(int i=0;i<n;i++){
rev[arr[i]] = i;
}
for(int i=0;i<m;i++){
int q = seg.query(a[i]+1, b[i]+1);
res[i] = rev[q];
}
return res;
}
