#include <iostream>
#include <fstream>
#define NMAX 100001
#define BUFF_SIZE 100001

using namespace std;

int n, m, A[NMAX];
ifstream in("cautbin.in");
ofstream out("cautbin.out");
char BUFF[BUFF_SIZE];
int pos = 0;

void Read(int &a)
{
    while (!isdigit(BUFF[pos]))
        if (++pos == BUFF_SIZE)
            in.read(BUFF,BUFF_SIZE), pos = 0;
    a = 0;
    while (isdigit(BUFF[pos]))
    {
        a = a * 10 + BUFF[pos] - '0';
        if (++pos == BUFF_SIZE)
            in.read(BUFF,BUFF_SIZE), pos = 0;
    }
}

int binar1(int key)
{
    int step, i = 0;
    for (step = 1; step <= n; step <<= 1);
    for ( ; step; step >>= 1)
        if (i + step <= n && A[i + step] <= key)
            i = i + step;
    if (A[i] == key)
        return i;
    return -1;
}

int binar2(int key)
{
    int step, i = 0;
    for (step = 1; step <= n; step <<= 1);
    for ( ; step; step >>= 1)
        if (i + step <= n && A[i + step] <= key)
            i = i + step;
    return i;
}

int binar3(int key)
{
    int step, i = 0;
    for (step = 1; step <= n; step <<= 1);
    for ( ; step; step >>= 1)
        if (i + step <= n && A[i + step] < key)
            i = i + step;
    return i + 1;
}

int main()
{
    Read(n);
    for (int i = 1; i <= n; i++)
        Read(A[i]);
    Read(m);
    int x, y;
    for (int i = 1; i <= m; i++)
    {
        Read(x); Read(y);
        switch(x)
        {
            case 0: out << binar1(y) << "\n"; break;
            case 1: out << binar2(y) << "\n"; break;
            case 2: out << binar3(y) << "\n"; break;
        }
    }
    in.close();
    out.close();
    return 0;
}