#include <iostream>
#include <fstream>

using namespace std;

int sir [100002];

int main()
{
    ifstream in ("cautbin.in");
    ofstream out ("cautbin.out");
    int n;
    in>>n;
    for(int i=0;i<n;i++)
        in>>sir[i];
    int m;
    in>>m;
    for(int op=1;op<=m;op++){
        int intrebare,numar,raspuns;
        in>>intrebare>>numar;
        int stanga=0,dreapta=n-1;
        int gasit=0;
        sir[n]=100000;
        if(intrebare==0)
        {
            while(!gasit)
            {//cout<<stanga<<endl;
                if(sir[stanga] == numar && sir[stanga+1] != numar){
                    raspuns=stanga;
                    gasit=1;
                    break;
                }
                if(sir[(stanga+dreapta)/2]<=numar)
                {
                    stanga=(stanga+dreapta)/2 + 1;
                }else if(sir[(stanga+dreapta)/2]>numar){
                    dreapta=(stanga+dreapta)/2 - 1;
                }
                if(dreapta<stanga)
                {
                    raspuns=-2;
                    break;
                }
            }
        }
        //gasit=0;
        if(intrebare == 1){
            //sir[n]=-10;
            if(op==3)
            cout<<stanga<<' '<<dreapta<<endl;
            while(!gasit)
            {//cout<<stanga<<endl;
                if(sir[stanga] <= numar && (sir[stanga+1] > numar || stanga+1>=n)){
                    raspuns=stanga;
                    gasit=1;
                    break;
                }
                if(sir[stanga-1] <= numar && sir[stanga] > numar){
                    raspuns=stanga-1;
                    gasit=1;
                    break;
                }
                if(sir[(stanga+dreapta)/2]<=numar)
                {
                    stanga=(stanga+dreapta)/2 + 1;
                }else if(sir[(stanga+dreapta)/2]>numar){
                    dreapta=(stanga+dreapta)/2 - 1;
                }
                if(dreapta<stanga)
                {
                    raspuns=-2;
                    break;
                }
            }

        }
        if(intrebare == 2){
            while(!gasit)
            {//cout<<stanga<<endl;
                /*if(op==15){
                    cout<<stanga<<' '<<dreapta<<endl;
                }*/
                if(sir[stanga] >= numar && sir[stanga-1] < numar){
                    raspuns=stanga;
                    gasit=1;
                    break;
                }
                if(sir[(stanga+dreapta)/2]<numar)
                {
                    stanga=(stanga+dreapta)/2 + 1;
                }else if(sir[(stanga+dreapta)/2]>=numar){
                    dreapta=(stanga+dreapta)/2;
                }
                if(dreapta<stanga)
                {
                    raspuns=-2;
                    break;
                }
            }

        }
        out<<raspuns+1<<'\n';
    }





    in.close();
    out.close();
    return 0;
}