#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(st<=dr){
                mij=(st+dr)>>1;
                if (a[mij]<=x) st=mij+1;
                else dr=mij-1;
            }
            if (x==a[dr]) g<<dr<<"\n";
        }
        else if(p==1){
            st=0;
            dr=n;
            while(st<=dr) {
                mij=(st+dr)>>1;
                if(a[mij]<=x) st=mij+1;
                else dr=mij-1;
            }
            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;
            }
            g<<st<<"\n";
        }
    }
    return 0;
}