#include <fstream>
using namespace std;
int v[100000],a[200000],N,i,M,j,st,dr,med,ind,ans;
int cautbin(int val)
{
    st=1;
    ind=0;
    dr=N;
    while(st<dr)
    {
        med=(st+dr)/2;
        if(v[med]<=val)
            st=med+1;
        if(v[med]>val)
            dr=med-1;
        ind=med;
        return ind;
    }
}
int main()
{
    ifstream f("cautbin.in");
    ofstream c("cautbin.out");
    f>>N;
    for(j=1;j<=N;j++)
        f>>v[j];
    f>>M;
    i=1;
    while(i<=2*M)
    {
        f>>a[i];
        if(a[i]==0)
        {
            i++;
            f>>a[i];
            ans=cautbin(a[i]);
            if(v[ans]>a[i])
                c<<"-1"<<'\n';
            else
                {
                    while(v[ans+1]==v[ans])
                         ans++;
                    c<<ans<<" "<<'\n';
                }
        }
        else
            if(a[i]==1)
            {
                i++;
                f>>a[i];
                ans=cautbin(a[i]);
                if(v[ans]>a[i])
                {
                    while(a[i]<v[ans])
                        ans--;
                }
                else
                {
                     while(v[ans+1]==a[i])
                         ans++;
                }
                c<<ans<<" "<<'\n';
            }
            else
                if(a[i]==2)
                {
                    i++;
                    f>>a[i];
                    ans=cautbin(a[i]);
                    if(v[ans]>a[i])
                    {
                        while(v[ans-1]>a[i])
                            ans--;
                    }
                    else
                    {
                        while(v[ans-1]==a[i])
                            ans--;

                    }
                    c<<ans<<" "<<'\n';
                }

        i++;
    }


    return 0;
}