#include<fstream>
using namespace std;
#define Max 100004

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

unsigned int N,M,poz[3],X,aux;
unsigned int V[Max];

void cb0(int left,int right){
    int mid;
    while(left<=right){
        mid = left + (right-left)/2;
        if(V[mid]<X){
                left=mid+1;
            }
            if(V[mid]>X){
                right=mid-1;
            }
            if(V[mid]==X){
                poz[0]=mid;
                left=mid+1;
            }
    }
}

void cb1(int left, int right){
    int mid;
    while(left<=right){
        mid = left + (right-left)/2;
        if(V[mid]<=X){
                poz[1]=mid;
                left =mid+1;
            }
            if(V[mid]>X){
                right=mid-1;
            }
    }
}

void cb2(int left, int right){
    int mid;
    while(left<=right){
        mid = left + (right-left)/2;
        if(V[mid]>=X){
                poz[2]=mid;
                right=mid-1;
            }
            if(V[mid]<X){
                left=mid+1;
            }
    }
}

int main(){

    fin>>N;
    for(unsigned int i=1;i<=N;i++){
        fin>>V[i];
    }

    fin>>M;
    for(unsigned int i=1;i<=M;i++){
        fin>>aux>>X;
        poz[0]=0;
        if(aux==0)
            cb0(1,N);
        if(aux==1)
            cb1(1,N);
        if(aux==2)
            cb2(1,N);
        if(aux==0 && !poz[0])
            fout<<"-1\n";
        else
            fout<<poz[aux]<<"\n";
    }

    return 0;
}