#include <cstdio>
#define limN 100001
using namespace std;

int n, m, v[limN];

int cautBin0 (int x)
{
    int pas = 1 << 17;
    int i = 0;
    while (pas)
    {
        if ( i+pas<=n && v[i+pas] <= x ) //cum stiu daca nu cumva "sar" de x-ul aflat pe cea mai mare pozitie? si ca
                                         //n-ar fi fost necesar "return i-1"?
                                         //!rasp: raman in "zona verde" deoarece il verificam v[i+pas], nu pe v[i]
            i += pas;
        pas /= 2;
    }
    if(v[i]!=x)
        return -1;
    return i;
}

int cautBin1 (int x)
{
    int pas = 1 << 17;
    int i = 0;
    while (pas)
    {
        if (i+pas <= n && v[i+pas] <= x ) //fac pasul daca sunt inca in "zona verde"
            i += pas;
        pas /= 2;
    }
    //dupa while, i se afla chiar in dreptul elementului mai mic sau egal cu x, de pe poz cea mai mare
    return i;
}

int cautBin2 (int x)
{
    int pas = 1 << 17;
    int i = 0;
    while (pas)
    {
        if ( i+pas<=n && v[i+pas] < x ) //fac pasii doar daca nu ajung la elemente mai mari sau egale cu x
            i += pas;
        pas /= 2;
    }
    //i se va afla exact inaintea unui elem care este mai mare sau egal cu x, deci incrementez i cu 1
    return i+1;
}

int main()
{
    int x, tip;
    freopen("cautbin.in","r",stdin);
    freopen("cautbin.out","w",stdout);
    scanf("%d", &n);
    for (int i=1; i<=n; ++i)
        scanf("%d", &v[i]);
    scanf("%d", &m);

    while (m--)
    {
        scanf("%d%d", &tip, &x);
        if (tip==0)
            printf("%d\n", cautBin0(x));

        else if (tip==1)
            printf("%d\n", cautBin1(x));

        else
            printf("%d\n", cautBin2(x));
    }


    return 0;
}