#include<fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n,i,T,m,p,u,tip,x,poz,a[100001];
int main()
{
    in>>n;
    for(i=1 ; i<=n; i++)in>>a[i];
    in>>T;
    while(T)
    {
        in>>tip>>x;
        p=1;
        u=n;
        poz=-1;
        if(tip<2)
        {
            do
            {
                m=(p+u)/2;
                if(a[m]==x)
                {
                    poz=m;
                    p=m+1;
                    while(p<=u)
                    {
                        m=(p+u)/2;
                        if(a[m]==x)
                        {
                            poz=m;
                            p=m+1;
                        }
                        else u=m-1;
                    }
                }
                else if(a[m]<x) p=m+1;
                else u=m-1;
            }
            while(p<=u);
            if(tip==1 && poz==-1) poz=u;
            out<<poz<<'\n';
        }
        else
        {
            do
            {
                m=(p+u)/2;
                if(a[m]==x)
                {
                    poz=m;
                    u=m-1;
                    while(p<=u)
                    {
                        m=(p+u)/2;
                        if(a[m]==x)
                        {
                            poz=m;
                            u=m-1;
                        }
                        else p=m+1;
                    }
                }
                else if(a[m]<x) p=m+1;
                else u=m-1;
            }
            while(p<=u);
            if(poz==-1) poz=p;
            out<<poz<<'\n';
        }
        T--;
    }
    out.close();
    return 0;
}