#include <bits/stdc++.h>

using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,nr,st,dr,i,j,poz,a[100005],intreb[100005],m,x;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)f>>a[i];
    f>>nr;
    for(j=1;j<=nr;j++)f>>intreb[j]>>x;
    st=1;
    dr=n;
    for(j=1;j<=nr;j++){
        if(intreb[j]==0){
                st=1;
        dr=n;
        poz=-1;
            while(st<=dr){
           m=(st+dr)/2;
            if(a[m]<=x){
                if(a[m]==x)poz=m;
                st=m+1;
            }
            else dr=m-1;
        }
        g<<poz<<'\n';
        }
        else if(intreb[j]==1){
        st=1;
        dr=n;
        poz=-1;
        while(st<=dr){
           m=(st+dr)/2;
            if(a[m]<=x){
                if(a[m]<=x)poz=m;
                st=m+1;
            }
            else dr=m-1;
        }
        g<<poz<<'\n';
        }
        else if(intreb[j]==2){
            st=1;
        dr=n;
        poz=0;
            while(st<=dr){
           m=(st+dr)/2;
            if(a[m]>=x){
                if(a[m]>=x)poz=m;
                dr=m-1;
            }
            else st=m+1;
        }
        g<<poz<<'\n';
        }
    }
    return 0;
}