#include <stdlib.h>
#include <string.h>
#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
int v2[40005],n;
stack <int> st;
void read_array(int subtask_id, const std::vector<int> &x) {
std::string bits;
n=x.size();
int i;
for (i=1;i<=n;i++)
{
v2[i]=x[i-1];
}
for (i=1;i<=n;i++)
{
while (!st.empty()&&v2[st.top()]<v2[i])
{
st.pop();
bits+="1";
}
st.push(i);
bits+="0";
}
save_to_floppy(bits);
}
int stanga[50005];
vector <pair <int,int> > queryuri;
pair <int,int> arb[160005];
void update(int st,int dr,int nod,int poz,int val)
{
if (st==dr)
{
arb[nod].first=val;
arb[nod].second=poz;
return;
}
int mij=(st+dr)/2;
if (poz<=mij)
{
update(st,mij,2*nod,poz,val);
}
else
{
update(mij+1,dr,2*nod+1,poz,val);
}
if (arb[2*nod].first<arb[2*nod+1].first)
{
arb[nod]=arb[2*nod];
}
else
{
arb[nod]=arb[2*nod+1];
}
}
pair <int,int> query(int st,int dr,int nod,int ua,int ub)
{
if (ua<=st&&dr<=ub)
{
return arb[nod];
}
int mij=(st+dr)/2; pair <int,int> r1={1e9,0},r2={1e9,0};
if (ua<=mij)
{
r1=query(st,mij,2*nod,ua,ub);
}
if (mij<ub)
{
r2=query(mij+1,dr,2*nod+1,ua,ub);
}
if (r1.first<r2.first)
{
return r1;
}
return r2;
}
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
n=N;
int i,poz;
while (!st.empty())st.pop();
poz=1;
for (i=0;i<bits.size();i++)
{
if (bits[i]=='0')
{
if (st.empty())
{
stanga[poz]=0;
}
else
{
stanga[poz]=st.top();
}
st.push(poz);
poz++;
}
else
{
st.pop();
}
}
for (i=1;i<=n;i++)
{
update(1,n,1,i,stanga[i]);
}
for (i=0;i<a.size();i++)
{
queryuri.push_back({a[i]+1,b[i]+1});
}
vector <int> answers;
for (i=0;i<queryuri.size();i++)
{
answers.push_back(query(1,n,1,queryuri[i].first,queryuri[i].second).second-1);
}
return answers;
}
