#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define sec second
void read_array(int subtask_id, const std::vector<int> &v) {
vector<pair<int, int>> isi;
int N = v.size();
for(int i = 0; i < N; i++){
isi.push_back({v[i], i});
}
sort(isi.begin(), isi.end());
int cur = 0;
for(auto &[val, idx] : isi){
val = ++cur;
}
int LOG = 0;
cur = 1;
while(cur <= N){
cur *= 2, LOG++;
}
sort(isi.begin(), isi.end(), [&](pair<int, int> a, pair<int, int> b){
return a.sec < b.sec;
});
string bits = "";
for(auto &[val, idx] : isi){
for(int j = 0; j < LOG; j++){
bits.push_back(((val >> j) & 1) + '0');
}
}
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> answers;
int Q = a.size();
vector<int> arr;
int LOG = 0, cur = 1;
while(cur <= N){
cur *= 2, LOG++;
}
for(int i = 0; i < N; i++){
int val = 0;
for(int j = i * LOG; j < i * LOG + LOG; j++){
val += (1LL << (j - i * LOG)) * (bits[j] == '1');
}
arr.push_back(val);
}
vector<int> lg(N + 5);
for(int i = 2; i <= N; i++) lg[i] = lg[i / 2] + 1;
vector<vector<pair<int, int>>> sp(N, vector<pair<int, int>>(LOG));
for(int log = 0; log < LOG; log++){
for(int i = 0; i < N; i++){
if(log == 0) sp[i][log] = {arr[i], i};
else{
if(i + (1LL << (log - 1)) < N) sp[i][log] = max(sp[i][log - 1], sp[i + (1LL << (log - 1))][log - 1]);
}
}
}
auto query = [&](int l, int r){
return max(sp[l][lg[r - l + 1]], sp[r - (1LL << lg[r - l + 1]) + 1][lg[r - l + 1]]).sec;
};
for(int i = 0; i < Q; i++){
answers.push_back(query(a[i], b[i]));
}
return answers;
}
