#include<stdio.h> 
int n,m,v[100025];
inline int Q1(int x){
    int bi,av,sai;
    for(bi=1,av=n;bi<=av;){
        sai=bi+(av-bi)/2;
        if(v[sai]>x)
			av=sai-1;
        else
			if(v[sai]<x)
				bi=sai+1;
        else
			return sai;
    }
    return -1;
}
inline int Q2(int x){
    int bi,av,sai,ul=0;
    for(bi=1,av=n;bi<=av;){
        sai=bi+(av-bi)/2;
        if (x>=v[sai])
			ul=sai,bi=sai+1;
        else
			av=sai-1;
    }
    return ul;
}
inline int Q3(int x){
    int bi,av,sai,ul=n+1;
    for(bi=1,av=n;bi<=av;){
        sai=bi+(av-bi)/2;
        if(v[sai]>=x)
			ul=sai,av=sai-1;
        else
			bi=sai+1;
    }
    return ul;
}
int main(void){
    int i,t,x;
    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=m;i>0;--i){
        scanf("%d%d",&t,&x);
        if(!t)
            printf("%d\n",Q1(x));
        else
			if(t==1)
				printf("%d\n",Q2(x));
        else
            printf("%d\n",Q3(x));
    }
	fclose(stdin);
	fclose(stdout);
	return 0;
}