#include <iostream>
#include <stdio.h>

using namespace std;

FILE *f=fopen("cautbin.in","r");
FILE *g=fopen("cautbin.out","w");

long long  v[100005],val;
int i,n,nr,m;


long long cautbin1(long long val)
{
    int l,r,mx,m;
    l=1;
    r=n;
    mx=0;
    while(l<=r)
    {
        m=(l+r)/2;
        if(val==v[m])
        {
            while(val==v[m])m++;
            return m-1;
        }
        if(val<v[m])r=m-1; else l=m+1;
    }
    return -1;
}

long long cautbin2(long long val)
{
    int l,r,mx,m;
    l=1;
    r=n;
    mx=0;
    while(l<=r)
    {
        m=(l+r)/2;
        if(v[m]<=val)
        {
            mx=m;
            l=m+1;
        }else r=m-1;
    }
    return mx;
}

long long cautbin3(long long val)
{
    int l,r,mx,m;
    l=1;
    r=n;
    mx=0;
    while(l<=r)
    {
        m=(l+r)/2;
        if(v[m]>=val)
        {
            mx=m;
            r=m-1;
        }else l=m+1;
    }
    return mx;
}

int main()
{
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    fscanf(f,"%lld",&v[i]);
    fscanf(f,"%d",&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%lld",&nr,&val);
        switch(nr)
        {
            case 0:{fprintf(g,"%lld\n",cautbin1(val));break;}
            case 1:{fprintf(g,"%lld\n",cautbin2(val));break;}
            case 2:{fprintf(g,"%lld\n",cautbin3(val));break;}
        }

    }
    fclose(g);
    return 0;
}