#include <iostream>
#include <fstream>

using namespace std;

int const N= 100001;

int caz0(int a[], int lo, int hi, int x){
    if(lo==hi)
        return lo;
    else{
        int mid= lo+ (hi-lo)/2;
        if(x >= a[mid])
            return (a,mid+1,hi,x);
        else
            return (a,lo,mid-1,x);


    }
}

int caz1(int a[], int lo, int hi, int x){
    if(lo==hi)
        return lo;
    else{
        int mid= lo+ (hi-lo)/2;
        if(x >= a[mid])
            return (a,mid+1,hi,x);
        else
            return (a,lo,mid-1,x);


    }
}
int caz2(int a[], int lo, int hi, int x){
    if(lo==hi)
        return lo;
    else{
        int mid= lo+ (hi-lo)/2;
        if(x > a[mid])
            return (a,mid+1,hi,x);
        else
            return (a,lo,mid-1,x);


    }
}

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");

    int t,n,caz,nr,a[N],sol;
    in>>n;
    for(int i=0;i<n;i++)
        in>>a[i];
    in>>t;
    for(int z=1;z<=t;z++){
        in>>caz>>nr;
        if(caz == 0)
            sol= caz0(a,0,n-1,nr);
        else if(caz == 1)
            sol= caz1(a,0,n-1,nr);
        else if(caz == 2)
            sol= caz2(a,0,n-1,nr);
        if(a[sol] != nr)
            sol= -1;
        if(sol != -1 && caz == 2)
            sol--;
        else if(sol != -1 && (caz == 1 || caz ==0))
            sol++;
        out<<sol<<"\n";
    }






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