#include <fstream>
#include<iostream>
using namespace std;
int v[100000],a[200000],N,i,M,j,ans;
int cautbin(int val)
{
    int i, step;

    for (step = 1; step < N; step <<= 1);

    for (i = 0; step; step >>= 1)

        if (i + step < N && v[i + step] <= val)

           i += step;

    return i;
}
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]==a[i])
                     ans++;
                c<<ans<<'\n';
            }
        }
        else
            if(a[i]==1)
            {
                i++;
                f>>a[i];
                ans=cautbin(a[i]);
                if(v[ans]!=a[i])
                {
                    while(v[ans]>a[i])
                        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]<=a[i])
                            ans++;
                    }
                    c<<ans<<'\n';
                }

        i++;
    }


    return 0;
}