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