#include <stdio.h>
#include <stdlib.h>
int a[10000];
int bin0(int x,int p,int r)
{
    int m;
    while(p<=r)
    {
        m=(p+r)/2;
        if(a[m]<=x)
            p=m+1;
        else
            r=m-1;
    }
    m=(p+r)/2;
    if(a[m]>x) m--;
    if(a[m]==x) return m;
        else return -1;
}
int bin1(int x,int p,int r)
{
    int m;
    while(p<r)
    {
        m=(p+r)/2;
        if(a[m]<=x)
            p=m+1;
        else
            r=m;
    }
    m=(p+r)/2;
    if(a[m]>x)
    m--;
    return m;
}
int bin2(int x,int p,int r)
{
    int m;
    while(p<r)
    {
        m=(p+r)/2;
        if(a[m]<x)
            p=m+1;
        else
            r=m;
    }
    m=(p+r)/2;
    if(a[m]<x)
    m++;
    return m;
}

int main()
{
    int n,i,j,m,el1,el2;
    FILE *f=fopen("cautbin.in","r");
    FILE *g=fopen("cautbin.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    fscanf(f,"%d",&a[i]);
    fscanf(f,"%d",&m);
    for(j=0;j<m;j++)
    {
        fscanf(f,"%d %d",&el1,&el2);
        if(el1==0)
            fprintf(g,"%d\n",bin0(el2,1,n));
        if(el1==1)
            fprintf(g,"%d\n",bin1(el2,1,n));
        if(el1==2)
            fprintf(g,"%d\n",bin2(el2,1,n));
    }
    return 0;
}