#include <fstream>
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int n,m,a[100001],dr,st,p,i,mij,x,ok;
int main ()
{
    f>>n;
    for(i=1;i<=n;++i) f>>a[i];
    f>>m;
    for(i=1;i<=m;++i) {
        f>>p>>x;
        if(p==0) {
            st=0;
            dr=n;
            while(dr-st>1) {
                mij=(st+dr)>>1;
                if(a[mij]>x) dr=mij;
                else st=mij;
            }
            if(x==a[st]) g<<st<<"\n";
        }
        else if(p==1){
            st=0;
            dr=n;
            while(st<=dr) {
                mij=(st+dr)>>1;
                if(a[mij]>x) dr=mij-1;
                else st=mij+1;
            }
            if(x>=a[dr]) g<<dr<<"\n";
        }
        else {
            st=0;
            dr=n;
            while(st<=dr) {
                mij=(st+dr)>>1;
               if(a[mij]<x) st=mij+1;
               else dr=mij-1;
            }
            if(x<=a[st]) g<<st<<"\n";
        }
    }
    return 0;
}