#include <stdio.h>

int S[100001],n;

int op1(int x)
{
    int mid,l,r;
    for (l=1,r=n; l<=r;)
     {  		
     mid = l + (r-l) / 2;
     if (x < S[mid]) r = mid-1;
     else if (S[mid] < x) l = mid+1;
     else return mid;
     }
return -1;
}

int op2(int x)
{
    int mid,l,r,last=0;
    for (l=1,r=n;l<=r;)
    {
    mid = l + (r-l) / 2;
    if (S[mid]<=x) last = mid, l = mid+1;
    else r = mid -1;
    }
return last;
}

int op3(int x)
{
    int mid,l,r,last=0;
    for (l=1,r=n;l<=r;)
    {
    mid = l + (r-l) / 2;
    if (S[mid]>=x) last = mid, r = mid-1;
    else l = mid +1;
    }
return last;
}

int main()
{
    FILE *in,*out;
    in = fopen("cautbin.in","r");
    out = fopen("cautbin.out","w");
    int m,o,x,i;
    fscanf(in,"%d",&n);
    for (i=1;i<=n;i++) fscanf(in,"%d",&S[i]);
    fscanf(in,"%d",&m);
    for (;m;m--)
    {
        printf("%d\n",m);
        fscanf(in,"%d %d",&o,&x);
        if (o==0) fprintf(out,"%d\n",op1(x));
        else if (o==1) fprintf(out,"%d\n",op2(x));
        else fprintf(out,"%d\n",op3(x));
    }
}