#include<fstream>
using namespace std;

int a[100002],N,i;
ofstream fout("cautbin.out");
ifstream fin("cautbin.in");

int binarySearch0(int x){
    int mid, hi = N, lo = -1;
    while (hi - lo > 1){
        mid = lo + (hi - lo)/2;
        if(a[mid] < x) lo = mid;
        else hi = mid;
    }
    if(hi == N || a[hi] != x) return -1;
    else return hi+1;
}
int binarySearch1(int x){
    int mid, hi = N, lo = -1;
    while (hi - lo > 1){
        mid = lo + (hi - lo)/2;
        if(a[mid] < x) lo = mid;
        else hi = mid;
    }
    if(hi == N || a[hi] != x){
        if(x > 0) return binarySearch1(x-1);
        else return -1;
    }
    else return hi+1;
}
int binarySearch2(int x){
    int mid, hi = N, lo = -1;
    while (hi - lo > 1){
        mid = lo + (hi - lo)/2;
        if(a[mid] <= x) lo = mid;
        else hi = mid;
    }
    if(hi == N || a[hi] != x){
        if(x > 0) return binarySearch1(x+1);
        else return -1;
    }
    else return hi+1;
}
int main()
{

    int M,i,sType,x;
    fin >> N;
    for(i = 0 ; i < N; i++){
        fin >> a[i];
    }
    fin >> M;
    for(i = 0; i < M; i++){
        fin >> sType >> x;
        switch(sType){
            case 0: fout << binarySearch0(x)<<"\n";
            break;
            case 1: fout << binarySearch1(x)<<"\n";
            break;
            case 2: fout << binarySearch2(x)<<"\n";
            break;
            default: break;
        }
    }
    fin.close();
    fout.close();
    return 0;
}