#include<iostream>
#include<fstream>
#define ll long long

using namespace std;

ifstream f("cautbin.in");
ofstream g("cautbin.out");

ll f0(ll a[],ll st,ll dr,ll key)
{
    ll m;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(a[m]<=key)
        st=m+1;
        else
            dr=m-1;

    }
    m=(st+dr)/2;
    if(a[m]>key)m--;
    if(a[m]==key) return m;
    return -1;


}
ll f1(ll a[],ll st,ll dr,ll key)
{
    ll m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(a[m]>=key)
            st=m+1;
        else
            dr=m;

    }
    m=(st+dr)/2;
    if(a[m]>key)
        --m;
    return m;


}
ll f2(ll a[],ll st,ll dr,ll key)
{
    ll m;
    while(st<dr)
    {
        m=(st+dr)/2;
        if(a[m]>key)
            st=m+1;
        else
            dr=m;
    }
    if(a[m]<key)
        ++m;
    return m;
}
int main()
{
    int n,m,i;
    f>>n;
    ll a[n+1],x,y;
    for(i=1;i<=n;i++)
        f>>a[i];
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        switch(x){
        case 0 : {g<<f0(a,1,n,y)<<"\n";
            break;}
        case 1 : {
            g<<f1(a,1,n,y)<<"\n";
            break;}
        case 2 : {
            g<<f2(a,1,n,y)<<"\n";
            break;}
        }
    }
    return 0;
}