#include <stdio.h>
#include <stdlib.h>
int binary_search(int *a,int x,int p,int r)
{

    int q;
    if(r<p)
        return -1;
    q=(r+p)/2;
    if(x<a[q])
       return binary_search(a,x,p,q-1);
    else
        if(x>a[q])
          return binary_search(a,x,q+1,r);
        else
            return q;
}
int main()
{
    int *a,n,m,i,el1,el2,k;
    FILE *f=fopen("cautbin.in","r");
    FILE *g=fopen("cautbin.out","w");
    fscanf(f,"%d",&n);
    a=malloc(n*sizeof(int));
    for(i=1;i<=n;i++)
        fscanf(f,"%d",&a[i]);
    fscanf(f,"%d",&m);
    for(i=0;i<m;i++)
    {
        fscanf(f,"%d %d",&el1,&el2);
        if(el1==0)
            {
                k=binary_search(a,el2,1,n);
                while(a[k]==el2 && k!=-1) k++; fprintf(g,"%d\n",--k);
            }
        if(el1==1)
            {
                k=binary_search(a,el2,1,n);
                while(a[k]!=el2 && k!=-1) k--; fprintf(g,"%d\n",k);
            }
        if(el1==2)
        {
            k=binary_search(a,el2,1,n);
            while(a[k]==el2&&k!=-1) k--; fprintf(g,"%d",k);
        }
    }
    return 0;
}