#include<stdio.h>
FILE *in,*out;
int n,m,i,tip,val;
long int v[100001];

int bsearch0(int,int,long int);
int bsearch1(int,int,long int);
int bsearch2(int,int,long int);

int main()
{
    in=fopen("cautbin.in","rt");
    out=fopen("cautbin.out","wt");
    fscanf(in,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(in,"%ld",&v[i]);
    fscanf(in,"%d",&m);
    while(m--)
    {
        fscanf(in,"%d %d",&tip,&val);
        if(!tip)
            fprintf(out,"%d\n",bsearch0(1,n,val));
        if(tip==1)
            fprintf(out,"%d\n",bsearch1(1,n,val));
        if(tip==2)
            fprintf(out,"%d\n",bsearch2(1,n,val));
    }

    return 0;
}

int bsearch0(int st,int dr,long int key)
{
    int mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<=key)
            st=mid+1;
        else
            dr=mid-1;
    }
    mid=(st+dr)/2;
    if(v[mid]>key)
        mid--;
    if(v[mid]==key)
        return mid;
    return -1;
}

int bsearch1(int st,int dr,long int key)
{
    int mid;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<=key)
            st=mid+1;
        else
            dr=mid-1;
    }
    mid=(st+dr)/2;
    if(v[mid]>key)
        mid--;
    return mid;
}

int bsearch2(int st,int dr,long int key)
{
    int mid;
    while(st<dr)
    {
        mid=(st+dr)/2;
        if(v[mid]<key)
            st=mid+1;
        else
            dr=mid-1;
    }
    mid=(st+dr)/2;
    if(v[mid]<key)
        mid++;
    return mid;
}