#include <cstdio>
int a[100001],n,x,m,tip;
FILE *f,*g;
int bsearch0(int left, int right, int value)
{
    while (left<=right)
    {
        int middle=(left+right)/2;
        if ((a[middle]==value && middle==n)||(a[middle]==value && a[middle+1]>value)) return middle;
        if (a[middle]==value && a[middle+1]==value) left=middle+1;
        if (a[middle]<value) left=middle+1;
        if (a[middle]>value) right=middle-1;
    }
    return -1;
}
int bsearch1(int left, int right, int value)
{
    while (left<=right)
    {
        int middle=(left+right)/2;
        if ((a[middle]<=value && middle==n)||(a[middle]<=value && a[middle+1]>value)) return middle;
        if (a[middle]<=value) left=middle+1;
        if (a[middle]>value) right=middle-1;
    }
    return -1;
}
int bsearch2(int left, int right, int value)
{
    while (left<=right)
    {
        int middle=(left+right)/2;
        if ((a[middle]>=value && middle==1)||(a[middle]>=value && a[middle-1]<value)) return middle;
        if (a[middle]>=value) right=middle-1;
        if (a[middle]<value) left=middle+1;
    }
    return -1;
}
int main()
{
    f=fopen("cautbin.in","r");
    g=fopen("cautbin.out","w");
    fscanf(f,"%d",&n);
    for (int i=1;i<=n;i++)
        fscanf(f,"%d",&a[i]);
    fscanf(f,"%d",&m);
    for (int i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&tip,&x);
        if (tip==0) fprintf(g,"%d\n",bsearch0(1,n,x));
        if (tip==1) fprintf(g,"%d\n",bsearch1(1,n,x));
        if (tip==2) fprintf(g,"%d\n",bsearch2(1,n,x));
    }
    fclose(f);
    fclose(g);
    return 0;
}