#include <cstdio>
int a[100001];
int main()
{
    FILE *f=fopen("cautbin.in","r");
    FILE *g=fopen("cautbin.out","w");
    int N,M,tip,x,i;
    fscanf(f,"%d",&N);
    for(i=1; i<=N; i++)
        fscanf(f,"%d",&a[i]);
    fscanf(f,"%d",&M);
    for(i=1; i<=M; i++)
    {
        fscanf(f,"%d%d",&tip,&x);
        int li, lf, m;
        if(tip==0)
        {
            li=1;lf=N;
            while(li<=lf)
            {
                m=(li+lf)/2;
                if(x>=a[m])
                    li=m+1;
                else
                    lf=m-1;
            }
            if( lf<1 || a[lf]!=x)
                fprintf(g, "-1\n");
            else
                fprintf(g, "%d\n", lf);
        }
        else if(tip==1)
        {
            li=1;lf=N;
            while(li<=lf)
            {
                m=(li+lf)/2;
                if(x>=a[m])
                    li=m+1;
                else
                    lf=m-1;
            }
            fprintf(g, "%d\n", lf);
        }
        else
        {
            li=1;lf=N;
            while(li<=lf)
            {
                m=(li+lf)/2;
                if(x<=a[m])
                    lf=m-1;
                else
                    li=m+1;
            }
            fprintf(g, "%d\n", li);
        }
    }
    return 0;
}