#include<bits/stdc++.h>
using namespace std;
const int N = 100020;
long long n, a[N];
int caut0(long long key){
	int st=1, dr=n, m;
	while(st<=dr){
		m=(st+dr)/2;
		if(a[m]<=key) st=m+1;
		else dr=m-1;
	}
	if(a[m]>key)m--;
	if(a[m]<key)m++;
	return (a[m]==key? m : -1);
}
int caut1(long long key){
	int st=1, dr=n, m;
	while(st<=dr){
		m=(st+dr)/2;
		if(a[m]<=key) st=m+1;
		else dr=m-1;
	}
	if(a[m]>key) m--;
	return m;
}
int caut2(long long key){
	int st=1, dr=n, m;
	while(st<=dr){
		m=(st+dr)/2;
		if(a[m]>=key) dr=m-1;
		else st=m+1;
	}
	if(a[m]<key)m++;
	return m;
}
int main(){
	freopen("cautbin.in", "r", stdin);
	freopen("cautbin.out", "w", stdout);
	scanf("%d", &n);
	int m;
	for(int i=1;i<=n;i++) scanf("%ld", &a[i]);
	scanf("%d", &m);
	while(m--){
		int x;
		long long y;
		scanf("%d%ld", &x, &y);
		if(x==0) printf("%d\n", caut0(y));
		if(x==1) printf("%d\n", caut1(y));
		if(x==2) printf("%d\n", caut2(y));
	}
	return 0;
}