#include <fstream>

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

            }
            g<<p<<'\n';
        }
        else{
             st=1;dr=n;p=0;
            while(st<=dr){
               mid=(st+dr)/2;
               if(v[mid]>=x){
                    dr=mid-1;
                    p=mid;
               }
               else
                if(v[mid]<x)
                    st=mid+1;


            }
            g<<p<<'\n';
        }
    }
    return 0;
}