#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;
#define inf 0xfffffff
#define MOD 1999999973

int n, m, a[100010];

int cb0(int x) {
	int l = 1, r = n, m;
	while (r-l>1) {
		m=(l+r)/2;
		if (a[m]>x)r=m; else l=m;
	}
	return a[r]==x?r:a[l]==x?l:-1;
}

int cb1(int x) {
	int l = 1, r = n, m;
	while (r-l>1) {
		m=(l+r)/2;
		if (a[m]>x)r=m; else l=m;
	}
	return a[r]<=x?r:l;
}

int cb2(int x) {
	int l = 1, r = n, m;
	while (r-l>1) {
		m=(l+r)/2;
		if (a[m]>x)l=m; else r=m;
	}
	return a[l]>=x?l:r;
}

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

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &op, &x);
		switch(op) {
			case 0:
				printf("%d\n", cb0(x));
				break;
			case 1:
				printf("%d\n", cb1(x));
				break;
			case 2:
				printf("%d\n", cb2(x));
				break;
		}
	}

	
	return 0;
}