#include <iostream>
#include <fstream>

using namespace std;

int n,m,a[100001];

int cautareBinara1(int st,int dr,int x)
{
    int mij;
    while(st<=dr)
    {
        mij=st+(dr-st)/2;
        if(x<a[mij])
            dr=mij-1;
        else
            st=mij+1;
    }
//    if(a[dr]==x)
//        return dr;
//    return -1;
    mij=st+(dr-st)/2;
    if(a[mij]>x)
        mij--;
    return mij;
}

int cautareBinara2(int st,int dr,int x)
{
    int mij;
    while(st<=dr)
    {
        mij=st+(dr-st)/2;
        if(x<a[mij])
            dr=mij-1;
        else
            st=mij+1;
    }
//    return dr;
    mij=st+(dr-st)/2;
    if(a[mij]>x)
        mij--;
    return mij;
}

int cautareBinara3(int st,int dr,int x)
{
    int mij;
    while(st<=dr)
    {
        mij=st+(dr-st)/2;
        if(x>a[mij])
            st=mij+1;
        else
            dr=mij-1;
    }
//    return st;
    if(a[mij]<x)
        mij++;
    return mij;
}

int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    fin>>m;
    for(int j=1;j<=m;j++)
    {
        int x,y;
        fin>>x>>y;
        if(x==0)
        {
            fout<<cautareBinara1(1,n,y)<<"\n";
        }
        if(x==1)
        {
            fout<<cautareBinara2(1,n,y)<<"\n";
        }
        if(x==2)
        {
            fout<<cautareBinara3(1,n,y)<<"\n";
        }
    }
    return 0;
}