#include <bits/stdc++.h>
using namespace std;

//MACROS
#define pb push_back
#define fi first
#define se second
#define rep(i, begin, end) for (int i = (begin); i < (end); i++)
#define per(i, begin, end) for (int i = (begin) - 1; i >= (end); i--)
typedef long long LL;
typedef pair <int,int> PII;

int n, a[1<<20], q;

int main() {
	//freopen("in.txt","r",stdin);
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);

	cin >> n;
	for (int i = 0; i < n; i++) scanf("%d", a + i);
	cin >> q;
	while (q--) {
        int t, x;
        scanf("%d %d", &t, &x);
        if (t == 0) {
            int it = lower_bound(a,a+n,x+1) - a - 1;
            if (a[it] == x) printf("%d\n", it+1);
            else printf("-1\n");
        } else if (t == 1) {
            printf("%d\n", lower_bound(a,a+n,x+1) - a);
        } else {
            printf("%d\n", upper_bound(a,a+n,x-1) - a + 1);
        }
	}
}