#include<cstdio>
#define mod 1999999973
using namespace std;

int n,m,tip,arg,i,j;
int sir[100001];

void citire () {
	freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
	scanf ("%d", &n);
	for (i=1; i<=n; i++){
		scanf ("%d", &sir[i]);
	}
}

int search0 (int v){
	int s=1, f=n, mid, p=-1;
	while (s<=f){
		mid=(s+f)/2;
		if (sir[mid]==v){p=mid; s=mid+1;}
		if (sir[mid]>v){f=mid-1;}
		if (sir[mid]<v){s=mid-1;}
	}
	return p;
}

int search1 (int v){
	int s=1, f=n, mid, p=0;
	while (s<=f){
		mid=(s+f)/2;
		if (sir[mid]<=v){s=mid+1; p=mid;}
		if (sir[mid]>v){f=mid-1;}
	}
	return p;
}

int search2 (int v){
	int s=1, f=n, mid, p=0;
	while (s<=f){
		mid=(s+f)/2;
		if (sir[mid]>=v){f=mid-1; p=mid;}
		if (sir[mid]<v){s=mid+1;}
	}
	return p;
}

int main(){
    
	citire();
	
	scanf ("%d", &m);
	for (i=1; i<=m; i++){
		scanf ("%d %d", &tip, &arg);
		if (tip==0){printf ("%d\n", search0(arg));}
		if (tip==1){printf ("%d\n", search1(arg));}
		if (tip==2){printf ("%d\n", search2(arg));}
	}

	return 0;
}