#include <stdio.h>
#include <stdlib.h>
int a[100001],n,m;
int cautbin0(int x)
{
    int inc=1,sf=n;
    while(inc<=sf)
    {
        int mij=(inc+sf)/2;
        if(a[mij]<=x)
            inc=mij+1;
        else sf=mij-1;
    }
    int mij=(inc+sf)/2;
    if(a[mij]>x)
        mij--;
    if(a[mij]==x)
        return mij;
    return -1;
}
int cautbin1(int x)
{
    int inc=1,sf=n;
    while(inc<sf)
    {
        int mij=(inc+sf)/2;
        if(a[mij]<=x)
            inc=mij+1;
        else sf=mij;
    }
    int mij=(inc+sf)/2;
    if(a[mij]>x)
        mij--;
    return mij;
}
int cautbin2 (int x)
{
    int inc=1,sf=n;
    while (inc < sf)
    {
        int mij = (inc + sf) / 2;
        if (a[mij] < x)
            inc = mij + 1;
        else
            sf = mij;
    }

    int mij = (inc + sf) / 2;
    if (a[mij] < x)
        ++ mij;
    return mij;
}
int main()
{
    FILE *f=fopen("cautbin.in","r");
    FILE *g=fopen("cautbin.out","w");
    fscanf(f,"%d ",&n);
    int i;
    for(i=1; i<=n; i++)
        fscanf(f,"%d ",a+i);
    fscanf(f,"%d ",&m);
    for(i=1; i<=m; i++)
    {
        int t,x;
        fscanf(f,"%d %d ",&t,&x);
        if(t==0)
            fprintf(g,"%d\n",cautbin0(x));
        if(t==1)
            fprintf(g,"%d\n",cautbin1(x));
        if(t==2)
            fprintf(g,"%d\n",cautbin2(x));
    }
    fclose(f);
    fclose(g);
    return 0;
}