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


using namespace std;

int V[100005];

int nr0(int f, int l, int val)

{

    int M;

    while(f<=l)

    {

        M=(f+l)/2;

        if (V[M]<=val)

            f=M+1;

        else

            l=M-1;

    }

    M=(f+l)/2;

    if(V[M]>val)

        M--;

    if(V[M]==val)

        return M;

    return -1;

}

int nr1(int f,int l, int val)

{

    int M,N=l;

    while(f<l)

    {

        M=(f+l)/2;

        if(V[M]<= val)

            f=M+1;

        else

            l=M;



    }

    M=(f+l)/2;

    if(V[M]>val)

        M--;

    return M;

}

int nr2(int f, int l, int val)

{

    int M;

     while(f<l)

    {

        M=(f+l)/2;

        if(V[M]<= val)

            f=M+1;

        else

            l=M;



    }

    M=(f+l)/2;

    if(V[M]<val)

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