#include <cstdio>
using namespace std;
int v[100000], n, s, d, m, ma;

int f0(int a)
{
    s=1;
	d=n;
    while(s<d){
        ma=m;
        m=(s+d)/2;
        if(ma==m)
			break;
        if(v[m]<=a)
			s=m;
        else 
			d=m-1;}
	while(v[d]>a)
		d--;
    if(v[d]==a)
		return d;
    return -1;
}

int f1(int a)
{
    s=1;
	d=n;
    while(s<d){
        ma=m;
        m=(s+d)/2;
        if(ma==m)
			break;
        if(v[m]<=a)
			s=m;
        else
			d=m-1;}
    while(v[d]>a)
		d--;
    return d;

}

int f2(int a)
{
    s=1;
	d=n;
    while(s<d){
        m=(s+d)/2;
        if(v[m]<a)
			s=m+1;
        else 
			d=m;}
    if(v[s]<a)
		s++;
    return s;
}

int main()
{
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    int i, m, f, e;
    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",&f,&e);
		switch(f){
		case 0:
			printf("%d\n",f0(e));
			break;
		case 1:
			printf("%d\n",f1(e));
			break;
		case 2:
			printf("%d\n",f2(e));
			break;
		default:
			break;}}
    return 0;
}