#include <cstdio>
using namespace std;

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

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

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

        if(target == Array[middle]){
            position = middle;
            if(task == 2) right = middle - 1;
            else left = middle + 1;
        }else if(target < Array[middle]){
            if(task == 2) position = middle;
            right = middle - 1;
        }else{
            if(task == 1) position = middle;
            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);
    printf("%d\n", Search(target, task));
}
return 0;
}