#include <iostream>
#include <cstdio>
#define Dmax 100100
using namespace std;

int v[Dmax]; int N,M;

int CAUTARE_0(int y)
{
    int i,j,m;
    i=1; j=N;
    while(i<=j)
    {
        m=(i+j)/2;
        if(v[m]<=y) i=m+1;
            else j=m-1;
    }
    m=(i+j)/2;

    if(v[m]>y) m--;
    if(v[m]==y) return m;
    return -1;
}

int CAUTARE_1(int y)
{
    int i,j,m;
    i=1; j=N;
    while(i<j)
    {
        m=(i+j)/2;
        if(y>=v[m]) i=m+1;
            else j=m;
    }
    m=(i+j)/2;
    if(v[m]>y) m--;
    return m;
}

int CAUTARE_2(int y)
{
    int i,j,m;
    i=1; j=N;
    while(i<j)
    {
        m=(i+j)/2;
        if(y>v[m]) i=m+1;
                else j=m;
    }
    m-(i+j)/2;
    if(v[m]<y) m++;
    return m;
}

int main()
{
    freopen("cautbin.in", "r", stdin);
    freopen("cautbin.out", "w", stdout);

    int i,j,k,x,m;

    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", &k, &x);
        switch(k)
        {
            case 0:
                { printf("%d",CAUTARE_0(x)); }break;
            case 1:
                { printf("%d",CAUTARE_1(x)); }break;
            case 2:
                { printf("%d",CAUTARE_2(x));}break;
        }
        printf("\n");
    }

    return 0;
}