#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
int steve[40001];
int vec[40001];
void read_array ( int subtask_id, const vector <int > & v )
{
    int vf=0;
    steve[0]=0;
    for(int i=0; i<v.size(); i++)
        vec[i+1]=v[i];
    string bits="";
    vec[0]=2e9;
    for(int i=1; i<=v.size(); i++)
    {
        while(vf&&vec[steve[vf]]<vec[i])
        {
            vf--;
            bits+='1';
        }
        steve[++vf]=i;
        bits+='0';
    }
    save_to_floppy(bits);
}
int st[40001][16];
std :: vector <int > solve_queries (int subtask_id,
                                    int N, const string & bits,
                                    const vector <int > &a,
                                    const vector <int > & b )
{
    int vf=0;
    steve[0]=0;
    vector <int> ans;
    ans.clear();
    for(int i=0,j=1; i<bits.size(); i++,j++)
    {
        while(bits[i]=='1')
        {
            i++;
            vf--;
        }
        st[j][0]=steve[vf];
        steve[++vf]=j;
    }
    for(int j=1; j<=15; j++)
        for(int i=1; i<=N; i++)
            st[i][j]=st[st[i][j-1]][j-1];
    for(int i=0; i<a.size(); i++)
    {
        int start=b[i]+1,pas=15;
        while(pas!=-1)
        {
            if(st[start][pas]>=a[i]+1)
                start=st[start][pas];
            pas--;
        }
        ans.push_back(start-1);
    }
    return ans;
}