#include <stdio.h>
#include <fstream>
using namespace std;
int v[100000];
int main(){
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);
    long long n,m2,st=1,dr,t,x,m=0,poz=-1;
    scanf("%d",&n);
    dr=n;
    for(int i=1; i<=n; ++i) scanf("%d",&v[i]);
    scanf("%d",&m2);
    for(int i=1; i<=m2; ++i){
        scanf("%d%d",&t,&x);
        if(t==0){
            while(st<=dr){
                m=(st+dr)/2;
                if(v[m]==x)
                    if(m>poz)
                        poz=m;
                if(x>=v[m])
                    st=m+1;
                else
                    dr=m-1;
            }
            printf("%d\n",poz);
        }
        else if(t==1){
            while(st<=dr){
                m=(st+dr)/2;
                if(v[m]<=x)
                    if(m>poz)
                        poz=m;
                if(x>=v[m])
                    st=m+1;
                else
                    dr=m-1;
            }
            printf("%d\n",poz);
        }
        else{
            poz=500000;
            while(st<=dr){
                m=(st+dr)/2;
                if(v[m]>=x)
                    if(m<poz)
                        poz=m;
                if(x<=v[m])
                    dr=m-1;
                else
                    st=m+1;
            }
            printf("%d\n",poz);
        }
        poz=-1;
        st=1;
        dr=n;
    }
    return 0;
}