#include <cstdio>
using namespace std;

int Array[100001], length, queries, task, target;

int Search0(int target){
    int left = 1, right = length, position = -1;

    while(left <= right){
        int middle = (left + right) / 2;

        if(target == Array[middle]){
            position = middle;
            left = middle + 1;
        }else if(target < Array[middle]){
            right = middle - 1;
        }else{
            left = middle + 1;
        }
    }return position;
}
int Search1(int target){
    int left = 1, right = length, position = -1;

    while(left <= right){
        int middle = (left + right) / 2;

        if(target == Array[middle]){
            position = middle;
            left = middle + 1;
        }else if(target < Array[middle]){
            right = middle - 1;
        }else{
            position = middle;
            left = middle + 1;
        }
    }return position;
}
int Search2(int target){
    int left = 1, right = length, position = -1;

    while(left <= right){
        int middle = (left + right) / 2;

        if(target == Array[middle]){
            position = middle;
            right = middle - 1;
        }else if(target < Array[middle]){
            position = middle;
            right = middle - 1;
        }else{
            left = middle + 1;
        }
    }return position;
}

int main(){

freopen("cautbin.in", "r", stdin);
freopen("cautbin.out", "w", stdout);

scanf("%d", &length);

for(int i = 1; i <= length; i++){
    scanf("%d", &Array[i]);
}scanf("%d", &queries);

for(int i = 1; i <= queries; i++){
    scanf("%d", &task);
    scanf("%d", &target);
    if(task == 0) printf("%d\n", Search0(target));
    if(task == 1) printf("%d\n", Search1(target));
    if(task == 2) printf("%d\n", Search2(target));
}return 0;
}