#include <stdio.h>
#include <stdlib.h>


int binary_search(unsigned int *arr,unsigned  int n,unsigned  int target)
{
    unsigned  int low=0,high=n-1,mid;

    while(low<=high)
    {
        mid=(high+low)/2;

        if(arr[mid]<=target)
            low=mid+1;
        else high=mid-1;
    }

    mid=(high+low)/2;

    if(arr[mid]>target) mid--;
    if(arr[mid]==target) return mid+1;
    return -1;

}
unsigned int binar1y_search(unsigned int *arr,unsigned  int n,unsigned  int target)
{
    unsigned int low=0,high=n-1,mid;
    while(low<high)
    {
        mid=(high+low)/2;

        if(arr[mid]<=target)
            low=mid+1;
        else high=mid;
    }

    mid=(high+low)/2;

    if(arr[mid]>target) mid--;

    return mid+1;

}
unsigned  int bina2ry_search(unsigned int *arr,unsigned  int n,unsigned  int target)
{
    unsigned int low=0,high=n-1,mid;
    while(low<high)
    {
        mid=(high+low)/2;

        if(arr[mid]<target)
            low=mid+1;
        else high=mid;
    }

    mid=(high+low)/2;

    if(arr[mid]<target) mid++;

    return mid+1;
}
int main() {

    FILE *f=fopen("cautbin.in","r");
    FILE *g=fopen("cautbin.out","w");

    if(!f || !g) exit(1);

    unsigned  int n,t,x;
    fscanf(f,"%u",&n);

    unsigned  int *arr=(unsigned  int *)calloc(n, sizeof(unsigned  int));

    for(unsigned  int i=0;i<n;i++)
        fscanf(f,"%u",&arr[i]);

    fscanf(f,"%u",&t);

    unsigned short int type;

    while(t--)
    {
        fscanf(f,"%hu %u",&type,&x);

        if(type==0) fprintf(g,"%d\n", binary_search(arr,n,x));
        else if(type==1) fprintf(g,"%d\n", binar1y_search(arr,n,x));
        else fprintf(g,"%d\n", bina2ry_search(arr,n,x));
    }

    free(arr);
    return 0;
}