#include<fstream>
#include <stdio.h>
#include <stdlib.h>
using namespace std; 
int v[100011],n;
int bsearch0(int x) {
	int min,max,mid;
	min=1;
	max=n;
	if(n==0) return -1;
	else {
		while(min<max) {
			mid=min+(max-min)/2;
			if(x>=v[mid])
				min=mid+1;
			else
				max=mid-1;
		}
		mid=(min+max)/2;
		if(v[mid]>x) mid--;
		if(v[mid]==x) return mid;
		else return -1;
	}
}
int bsearch1(int x) {
	int min,max,mid;
	min=1;
	max=n;
	while(min<max) {
		mid=(min+max)/2;
		if(v[mid]<=x)
			min=mid+1;
		else
			max=mid;
	}
	mid=(min+max)/2;
	if(v[mid]>x) mid--;
	return mid;
}
int bsearch2(int x) {
	int min,max,mid;
	min=1;
	max=n;
	while(min<max) {
		mid=(min+max)/2;
		if(v[mid]<x) 
			min=mid+1;
		else 
			max=mid;
	}
	mid=(min+max)/2;
	if(v[mid]<x) mid++;
	return mid;
}
int main() {
	int m,x,y,i;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d", &n);
	for (i = 1; i <= n; ++ i)
		scanf("%d", &v[i]);
	scanf("%d", &m);
	for(i=1;i<=m;i++) {
		scanf("%d%d", &x, &y);
		if (x==0)
			printf("%d\n", bsearch0(y));
		if (x==1)
			printf("%d\n", bsearch1(y));
		if (x==2)
			printf("%d\n", bsearch2(y));
	}
	return 0;
}