#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include "floppy.h"
using namespace std;
int const MAXN=2e4+10,LG=15;
int mx[MAXN][LG]={};
int get(int l,int r)
{
int lg=log2(r-l+1);
return max(mx[l][lg],mx[r+1-(1<<lg)][lg]);
}
void read_array(int subtask_id, const std::vector<int> &V) {
int n=V.size();
int lg=log2(n)+1;
vector<int>x,v;
for (auto i:V)
x.push_back(i);
sort(begin(x),end(x));
v=x;
for (int i=0;i<n;i++)
v[i]=lower_bound(begin(x),end(x),V[i])-begin(x);
string bits="";
for (int i=0;i<n;i++)
{
for (int j=0;j<lg;j++)
{
if ((1<<j)&v[i])
bits+='1';
else
bits+='0';
}
}
save_to_floppy(bits);
}
std::vector<int> solve_queries(int subtask_id, int n,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
vector<int>ans;
vector<int>arr;
int lg=log2(n)+1;
for (int i=0;i<n;i++)
{
arr.push_back(0);
for (int j=0;j<lg;j++)
{
if (bits[lg*i+j]=='1')
arr.back()+=(1<<j);
}
}
for (int i=0;i<n;i++)
mx[i][0]=arr[i];
for (int i=1;(1<<i)<=n;i++)
for (int j=0;j+(1<<i)-1<n;j++)
mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
for (int i=0;i<a.size();i++)
{
int l,r;
l=a[i],r=b[i];
int mx=get(l,r);
int st=l-1,en=r;
while (st+1<en)
{
int mid=(st+en)/2;
if (get(l,mid)==mx)
en=mid;
else
st=mid;
}
ans.push_back(en);
}
return ans;
}
