#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
const int M = 40000, L = 16;
int maxx[M][L];
pair<int,int> get(int l,int r)
{
int b=31-__builtin_clz(r-l);
return {maxx[l][b],maxx[r-(1<<b)][b]};
}
void read_array(int subtask_id, const vector<int> &a)
{
string s;
int n=a.size();
int lg=31-__builtin_clz(n-1);
set<int> se;
for (int i=0;i<n;i++) se.insert(a[i]);
map<int,int> ind;
for (int i:se) ind[i]=ind.size();
vector<int> v;
for (int i=0;i<n;i++)
v.push_back(ind[a[i]]);
for (int i=0;i<n;i++)
for (int p=lg;p>=0;p--)
s+=char('0'+(v[i]>>p)%2);
save_to_floppy(s);
}
vector<int> solve_queries(int subtask_id, int n,
const string &bits,
const vector<int> &a, const vector<int> &b) {
vector<int> ans;
int lg=31-__builtin_clz(n-1);
vector<int> v(n);
int id=0;
for (int i=0;i<n;i++)
for (int p=lg;p>=0;p--)
if (bits[id++]=='0')
v[i]=v[i]*2;
else
v[i]=v[i]*2+1;
for (int i=0;i<n;i++) maxx[i][0]=i;
for (int p=1;p<L;p++)
for (int i=0;i+(1<<p)<=n;i++)
{
maxx[i][p]=maxx[i][p-1];
if (v[maxx[i+(1<<p-1)][p-1]]>v[maxx[i][p-1]])
maxx[i][p]=maxx[i+(1<<p-1)][p-1];
}
for (int i=0;i<a.size();i++)
{
pair<int,int> p=get(a[i],b[i]+1);
if (v[p.first]>v[p.second])
ans.push_back(p.first);
else
ans.push_back(p.second);
}
return ans;
}
