#include <stdio.h>
int n,m,i,t[100001],tip,x;
int cauta1(int st,int dr,int x)
{
    int m,sol=-1;
    while (st<=dr){
        m=(st+dr)/2;
        if (t[m]==x) {
            sol=m;
            st=m+1;
        } else
        if (t[m]>x) dr=m-1; else st=m+1;
    }
    return sol;
}
int cauta2(int st,int dr,int x)
{
    int m,sol=0;
    while (st<=dr){
        m=(st+dr)/2;
        if (t[m]<=x) {
            sol=m;
            st=m+1;
        }else dr=m-1;
    }
    return sol;
}
int cauta3(int st,int dr,int x)
{

    int m,sol=0;
    while (st<=dr){
        m=(st+dr)/2;
        if (t[m]>=x){
            sol=m;
            dr=m-1;
        } else st=m+1;
    }
    return sol;
}
int main(){
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&t[i]);
scanf("%d",&m);
for (i=1;i<=m;i++){
     scanf("%d%d",&tip,&x);
     switch(tip){
     case 0:printf("%d\n",cauta1(1,n,x)); break;
     case 1:printf("%d\n",cauta2(1,n,x)); break;
     case 2:printf("%d\n",cauta3(1,n,x)); break;
}
}
return 0;
}