#include<stdio.h>

using namespace std;

int v[100000],m,n,i,op,x;

int cautbin(int x,int ls,int ld)
{
    int mid, ok=0;;
    while (ls<ld-1 && ok==0)
    {
        mid=(ls+ld)/2;
        if (x!=v[mid]) ok=1;
           else
        if (x<v[mid]) ld=mid;
            else
        if (x>=v[mid])   ls=mid;

    }
    if ((ls==ld-1) || (x!=v[ls])) return -1;
        else return ls;
}

int cautbin1(int x,int ls,int ld)
{
    int mid;
    while (ls<ld-1)
    {
        mid=(ls+ld)/2;
        if (x<v[mid]) ld=mid;
            else ls=mid;
    }
    return ls;
}

int cautbin2(int x,int ls,int ld)
{
    int mid;
    while (ls<ld-1)
    {
        mid=(ls+ld)/2;
        if (x>v[mid]) ls=mid;
            else ld=mid;

    }
    return ld;
}
int main()
{
    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",&v[i]);
    fscanf(f,"%d",&m);
    for (i=1;i<=m;i++)
        {
            fscanf(f,"%d%d",&op,&x);
            if (op==0) fprintf(g,"%d\n",cautbin(x,1,n+1));
                else
                    if (op==1) fprintf(g,"%d\n",cautbin1(x,1,n+1));
                else fprintf(g,"%d\n",cautbin2(x,1,n+1));

        }

    fclose(f);
    fclose(g);


    return 0;
}