///#include <iostream>
#include <fstream>
using namespace std;
int v[100001];
int cbin0(int n, int p)
{
    int st = 1, dr = n, mij;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] <= p)
        {
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    mij = (st + dr) / 2;
    if (v[mij] > p)
        mij--;
    if (v[mij] == p)
    {
        return mij;
    }
    return -1;
}
int cbin1(int n, int p)
{
    int st = 1, dr = n, mij, x = n;
    while (st < dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] <= p)
        {
            st = mij + 1;
        }
        else
        {
            dr = mij;
        }
    }
    mij = (st + dr) / 2;
    if (v[mij] > p)
    {
        mij--;
    }
    return mij;
}
int cbin2(int n, int p)
{
    int st = 1, dr = n, mij;
    while (st < dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] < p)
        {
            st = mij + 1;
        }
        else
        {
            dr = mij;
        }
    }
    mij = (st + dr) / 2;
    if (v[mij] < p)
    {
        mij++;
    }
    return mij;
}
ifstream cin("cautbin.in");
ofstream cout("cautbin.out");
int main()
{
    int N, M, x, T, y;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> v[i];
    }
    cin >> M;
    for (int j = 1; j <= M; j++)
    {
        cin >> x >> y;
        if (x == 0)
        {
            cout << cbin0(N, y) << '\n';
        }
        if (x == 1)
        {
            cout << cbin1(N, y) << '\n';
        }
        if (x == 2)
        {
            cout << cbin2(N, y) << '\n';
        }
    }

}