#include <cstdio>

using namespace std;

int n, m;
int sir[100005];

int operatie;
int valoare;

void citire()
{
    scanf("%d", &n);

    for(int i = 0; i < n; i++)
    {
        scanf("%d", &sir[i]);
    }

    scanf("%d", &m);
}

void citireQuerry()
{
    scanf("%d %d", &operatie, &valoare);
}

int cautareBinara0(int st, int dr)
{
    while(st <= dr)
    {
        int m = (st + dr) / 2;

        if(valoare <= sir[m])
        {
            st = m + 1;
        }
        else if(valoare > sir[m])
        {
            dr = m - 1;
        }
    }

    m = (st + dr) / 2;

    if(sir[m] > valoare)
    {
        m--;
    }

    if(sir[m] == valoare)
    {
        return m + 1;
    }
    else
    {
        return -1;
    }
}

int cautareBinara1(int st, int dr)
{
    while(st <= dr)
    {
        int m = (st + dr) / 2;

        if(valoare <= sir[m])
        {
            st = m + 1;
        }
        else if(valoare > sir[m])
        {
            dr = m - 1;
        }
    }

    m = (st + dr) / 2;

    if(sir[m] > valoare)
    {
        m--;
    }

    if(sir[m] <= valoare)
    {
        return m + 1;
    }
    else
    {
        return -1;
    }
}

int cautareBinara2(int st, int dr)
{
    while(st <= dr)
    {
        int m = (st + dr) / 2;

        if(valoare > sir[m])
        {
            st = m + 1;
        }
        else if(valoare <= sir[m])
        {
            dr = m - 1;
        }
    }

    m = (st + dr) / 2;

    if(sir[m] < valoare)
    {
        m++;
    }

    if(sir[m] >= valoare)
    {
        return m + 1;
    }
    else
    {
        return -1;
    }
}


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

    citire();

    for(int k = 0; k < m; k++)
    {
        citireQuerry();

        int rasp = -1;

        if(operatie == 0)
        {
            rasp = cautareBinara0(0, n - 1);
        }
        else if(operatie == 1)
        {
            rasp = cautareBinara1(0, n - 1);
        }
        else if(operatie == 2)
        {
            rasp = cautareBinara2(0, n - 1);
        }

        printf("%d\n", rasp);
    }

    return 0;
}