#include <stdlib.h>
#include <string.h>
#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;
void read_array(int subtask_id, const vector<int> &v) {
int n = v.size();
int l = __lg(n);
vector<pair<int, int>> vq {};
for (int i = 0; i < n; i++) {
vq.push_back({v[i], i});
}
vector<int> ord (n, -1);
sort(vq.begin(), vq.end());
for (int i = 0; i < n; i++) {
ord[vq[i].second] = i;
}
string bits = "";
for (int i = 0; i < n; i++) {
for (int j = 0; j <= l; j++) {
if ((ord[i] >> j) & 1) bits += "1";
else bits += "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) {
int l = __lg(N);
vector<int> ord (N, 0);
int cur = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j <= l; j++) {
if (bits[cur] == '1') ord[i] += 1 << j;
cur++;
}
}
int k = sqrt(N);
int nk = ceil(N/(double) k);
vector<int> vb (nk, -1);
vector<int> vind (nk, -1);
for (int i = 0; i < N; i++) {
if (vb[i/k] < ord[i]) {
vb[i/k] = ord[i];
vind[i/k] = i;
}
}
vector<int> ans (a.size(), 0);
for (int i = 0; i < a.size(); i++) {
int sol = -1;
int id = -1;
int l = a[i];
int r = b[i];
while (l <= r) {
if (l%k == 0 && l + N/k <= r) {
if (sol < vb[l/k]) {
sol = vb[l/k];
id = vind[l/k];
}
l += N/k;
} else {
if (sol < ord[l]) {
sol = ord[l];
id = l;
}
l++;
}
}
ans[i] = id;
}
return ans;
}
