#include"floppy.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
int getlog(long long n) { return 63-__builtin_clzll(n); }
void read_array(int subtask_id,const vector<int> &v)
{
string s;
int n=v.size();
vector<int> val=v,lay(n);
vector< vector<ii> > sp(22);
sort(val.begin(),val.end());
for(int i=0;(1<<i)<=n;i++) sp[i].resize(n);
for(int i=0;i<n;i++) sp[0][i]={lower_bound(val.begin(),val.end(),v[i])-val.begin(),i};
for(int i=1;(1<<i)<=n;i++) for(int j=0;j<=n-(1<<i);j++) sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1<<(i-1))]);
stack<ii> Q;
Q.push({0,n-1});
while(!Q.empty())
{
ii a=Q.top();
Q.pop();
int lg=getlog(a.se-a.fi+1),mxpos=max(sp[lg][a.fi],sp[lg][a.se-(1<<lg)+1]).se;
ii b={a.fi,mxpos-1},c={mxpos+1,a.se};
string t;
if(c.fi<=c.se)
{
int lg2=getlog(c.se-c.fi+1),mxpos2=max(sp[lg2][c.fi],sp[lg2][c.se-(1<<lg2)+1]).se;
Q.push(c),t='1'+t;
}
else t='0'+t;
if(b.fi<=b.se)
{
int lg2=getlog(b.se-b.fi+1),mxpos2=max(sp[lg2][b.fi],sp[lg2][b.se-(1<<lg2)+1]).se;
Q.push(b),t='1'+t;
}
else t='0'+t;
s+=t;
}
save_to_floppy(s);
}
vector<int> solve_queries(int subtask_id,int n,const string &s,const vector<int> &a,const vector<int> &b)
{
stack<int> st;
st.push(0);
vector<int> ans,lay(n);
int val=0,pos=0,cnt=0,it=0;
while(!st.empty())
{
int a=st.top();
st.pop();
if(a==-1) lay[pos++]=cnt;
else if(a==-2) cnt--;
else
{
bool lt=s[it*2]-'0',rt=s[it*2+1]-'0';
cnt++,it++;
st.push(-2);
if(rt) st.push(0);
st.push(-1);
if(lt) st.push(0);
}
}
vector< vector<ii> > sp(22);
for(int i=0;(1<<i)<=n;i++) sp[i].resize(n);
for(int i=0;i<n;i++) sp[0][i]={lay[i],i};
for(int i=1;(1<<i)<=n;i++) for(int j=0;j<=n-(1<<i);j++) sp[i][j]=min(sp[i-1][j],sp[i-1][j+(1<<(i-1))]);
for(int i=0;i<a.size();i++)
{
int l=a[i],r=b[i],lg=getlog(r-l+1);
ans.push_back(min(sp[lg][l],sp[lg][r-(1<<lg)+1]).se);
}
return ans;
}
