#include <bits/stdc++.h>
using namespace std;
int N, i, Q, Cod;
int A[100005], Val;
int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    scanf("%d", &N);
    for(i = 0; i < N; i++) scanf("%d", &A[i]);
    scanf("%d", &Q);
    while(Q--) {
        scanf("%d%d", &Cod, &Val);
        if(Cod == 0) {
            int Poz = upper_bound(A, A + N, Val) - A - 1;
            if(A[Poz] == Val && Poz >= 0 && Poz < N) printf("%d\n", Poz);
            else printf("-1\n");
        }
        else if(Cod == 1) {
        int Poz = upper_bound(A, A + N, Val) - A - 1;
            if(A[Poz] <= Val) printf("%d\n", Poz);
            else printf("-1\n");
        }
        else {
            int Poz = lower_bound(A, A + N, Val) - A;
            if(A[Poz] >= Val) printf("%d\n", Poz);
            else printf("-1\n");
        }
    }
    return 0;

}