#include <stdlib.h>
#include <stdio.h>
using namespace std;
int V[100005];
int nr0(int f, int l, int key)
{
    int M;
    while(f<=l)
    {
        M=(f+l)/2;
        if (V[M]<=key)
            f=M+1;
        else
            l=M-1;
    }

    M=(f+l)/2;

    if(V[M]>key) M--;
    if(V[M]==key)
        return M;
    return -1;
}
int nr1(int f,int l, int key)
{
    int M,N=l;
    while(f<l)

    {

        M=(f+l)/2;

        if(V[M]<= key)

            f=M+1;

        else

            l=M;



    }

    M=(f+l)/2;

    if(V[M]>key)

        --M;

    return M;

}

int nr2(int f, int l, int key)

{

    int M;

     while(f<l)

    {

        M=(f+l)/2;

        if(V[M]< key)

            f=M+1;

        else

            l=M;
    }
    M=(f+l)/2;
    if(V[M]<key)
        ++M;
    return M;
}
int main () {
    int i, N, M, tip, val;

    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);

    while (M --){
          scanf("%d%d", &tip, &val);
          if (tip == 0)
             printf("%d\n", nr0(1, N, val));
          if (tip == 1)
             printf("%d\n", nr1(1, N, val));
          if (tip == 2)
             printf("%d\n", nr2(1, N, val));
    }
    exit(0);
}