#include <stdio.h>
#include <stdlib.h>
int v[100003];
int tip0(int p,int u,int val)
{
    int m;
    while(p<=u)
    {
        m=(u+p)/2;
        if(v[m]<=val)
        {
            p=m+1;
        }else{
            u=m-1;
        }
    }
    m = (p + u) / 2;
    if(v[m]>val)return --m;
    if(v[m]==val)
        return m;
    return -1;
}
int tip1(int p,int u,int val)
{
    int m;
    while(p<u)
    {
        m=(p+u)/2;
        if(v[m]<=val)
        {
            p=m+1;
        }else{
            u=m;
        }
    }
        m = (p + u) / 2;
    if(v[m]>val)
        return --m;
    return m;
}
int tip2(int p,int u,int val)
{
    int m;
    while(p<u)
    {
        m=(p+u)/2;
        if(v[m]<val)
        {
            p=m+1;
        }else{
            u=m;
        }
    }
        m = (p + u) / 2;
    if(v[m]<val)return ++m;
    return m;
}
int main()
{
    FILE *in,*out;
    in=fopen("cautbin.in","r");
    out=fopen("cautbin.out","w");
    int i,n,k,tip,val;
    fscanf(in,"%d\n",&n);
    for(i=1;i<=n;i++)
    {
        fscanf(in,"%d",&v[i]);
    }
    fscanf(in,"%d",&k);
    for(i=1;i<=k;i++)
    {
        fscanf(in,"%d %d\n",&tip,&val);
        if(tip==0)
        {
            fprintf(out,"%d\n",tip0(1,n,val));
        }
        if(tip==1)
        {
            fprintf(out,"%d\n",tip1(1,n,val));
        }
        if(tip==2)
        {
            fprintf(out,"%d\n",tip2(1,n,val));
        }
    }
    return 0;
}