#include <stdio.h>

int v[100001];
int bin_search0(int lo, int hi,int val)
{
    int mid;
    while(lo <= hi)
    {
        mid = (hi+lo)/2;
        if(v[mid] <= val)
            lo = mid +1;
        else
            hi = mid -1;
    }
    mid = (hi+lo)/2;
    if(v[mid] > val)
        mid--;
    if(v[mid] == val)
        return mid;
    return -1;
}

int bin_search1(int lo, int hi,int val)
{
    int mid;
    while(lo < hi)
    {
        mid = (hi+lo)/2;
        if(v[mid] <= val)
            lo = mid +1;
        else
            hi = mid;
    }
    mid = (hi+lo)/2;
    if(v[mid] > val)
        --mid;
    return mid;
}

int bin_search2(int lo, int hi,int val)
{
    int mid;
    while(lo < hi)
    {
        mid = (hi+lo)/2;
        if(v[mid] <= val)
            lo = mid +1;
        else
            hi = mid;
    }
    mid = (hi+lo)/2;
    if(v[mid] < val)
        ++mid;
    return mid;
}

int main()
{
    int n,m,i,x,vecin;
    int opt;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d",&n);
    for(i = 1; i <= n; i++)
        scanf("%d", &v[i]);
    scanf("%d",&m);
    for(i = 1; i <= m; i++)
    {
        scanf("%d %d",&opt,&vecin);
        if(opt == 0)
            printf("%d\n",bin_search0(1,n,vecin));
        if(opt == 1)
            printf("%d\n",bin_search1(1,n,vecin));
        if(opt == 2)
            printf("%d\n",bin_search2(1,n,vecin));

    }
    return 0;
}