#include <iostream>
#include <fstream>
#define MAXN 10001
#define MAX(a,b) ( (a) > (b) ? (a) : (b))

using namespace std;

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

int N,M,v[MAXN];

void cit(){
    in>>N;
    for(int i = 1 ; i <= N; i ++){
        in>>v[i];
    }
}
int cautbin_0(int nr){
    int mid,st = 1,dr = N;
    while(st <= dr){

        mid = (st + dr)/2;
        if(v[mid] > nr){
            dr = mid - 1;
        }else if(v[mid] < nr){
            st = mid  + 1;
        }else if(v[mid] == nr){
            break;
        }
    }
    mid = (st + dr)/2;
    if(v[mid + 1] == nr){
        return mid +1;
    }else if(v[mid] == nr){
        return mid;
    }else{
        return -1;
    }
}
int cautbin_1(int nr){
    int mid,st = 1,dr = N;
    while(st <= dr){

        mid = (st + dr)/2;
        if(v[mid] > nr){
            dr = mid - 1;
        }else if(v[mid] < nr){
            st = mid  + 1;
        }else if(v[mid] == nr){
            return cautbin_0(nr);
        }
    }
    mid = (st + dr)/2;
    if(v[mid] <= nr){
        return mid;
    }
}
int cautbin_2(int nr){
    int mid,st = 1,dr = N;
    while(st <= dr){

        mid = (st + dr)/2;
        if(v[mid] >= nr){
            dr = mid - 1;
        }else if(v[mid] <= nr){
            st = mid  + 1;
        }
    }
    mid = (st + dr)/2;
    if(v[mid+1] >= nr){
        return mid+1;
    }else if(v[mid] >= nr){
        return mid;
    }
}

int main()
{
    cit();
    in>>M;
    for(int i = 1 ; i <= M; i ++){
        int a, nr;
        in>>a>>nr;
        if(a == 0){
            out<<cautbin_0(nr)<<"\n";
        }else if(a == 1){
            out<<cautbin_1(nr)<<"\n";
        }else{
            out<<cautbin_2(nr)<<"\n";
        }
    }
    return 0;
}