#include <fstream>
//#include <iostream>

using namespace std;

#define LE 100666
#define cout g

ifstream f("cautbin.in");
ofstream g("cautbin.out");

int A[LE];

int bs1(int left,int right,int value)

{
    if (left==right) return (A[left]==value? left :-1);

    while (left<right)
    {
        int mij=(left+right+1)/2;
        if (A[mij]<=value)  left=mij;
        else  right=mij-1;
    }

    if (left>right) return -1;
    return (A[left]==value? left :-1);
}

int bs2(int left,int right,int value)
{
    if (left==right) return right;

    while (left<right)
    {
        int mij=(left+right+1)/2;
        if (A[mij]<=value) left=mij;
        else right=mij-1;
    }
    return left;
}


int main()
{
    int n,m,i,typ,val;

    f>>n;
    for(i=1; i<=n; ++i) f>>A[i];
    f>>m;

    for(i=1; i<=m; ++i,cout<<'\n')
    {
        f>>typ>>val;
        ++typ;
        if (typ==1) cout<<bs1(1,n,val);
        if (typ==2) cout<<bs2(1,n,val);

        if (typ==3)
        {
            if (A[1]>=val)
                cout<<1;
            else
                cout<<bs2(1,n,val-1)+1;
        }
    }

    return 0;
}