#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[100007],M,N;
int cautbin(int x)
{
    int start=0;
    int step=1;
    for(; step<=N; step<<=1);
    for(; step; step>>=1)
    {
        int index=start+step;
        if(index>N) continue;
        if(v[index]<=x)start=index;
    }
    return start;
}
int main()
{
    fin>>N;
    for(int i=1; i<=1; i++)
    {
        fin>>v[i];
    }
    fin>>M;
    for(int j=1; j<=M; j++)
    {
        int val,x;
        fin>>val>>x;

        if(val==0)
        {
            if(v[cautbin(x)]==x)
                fout<<cautbin(x);
            else
                fout<<-1;
        }
        if(val==1)
            fout<<cautbin(x);
        if(val==2)
            fout<<cautbin(x-1)+1;
    }
}