#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int CautBin0(int v[], int n, int val)
{
    int st, dr, mij, pos = -1;
    st = 1;
    dr = n;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] == val)
        {
            pos = mij;
            st = mij + 1;
        }
        else if (v[mij] < val)
            st = mij + 1;
        else // v[mij] > val
            dr = mij - 1;
    }
    return pos;
}

int CautBin1(int v[], int n, int val)
{
    int st, dr, mij, pos = -1;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] <= val) {
            st = mij + 1;
            pos = mij;
        }
        else dr = mij - 1;
    }
    return pos;
}

int CautBin2(int v[], int n, int val)
{
    int st, dr, mij, pos = -1;
    st = 1;
    dr = n;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij] >= val)
        {
            pos = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    return pos;
}

int main()
{
    ifstream fin ("cautbin.in");
    ofstream fout ("cautbin.out");
    int n, a[100001];
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    int m;
    fin >> m;
    while(m--)
    {
        int op, x;
        fin >> op >> x;
        if (op == 0)
            fout << CautBin0(a, n, x) << "\n";
        else if (op == 1)
            fout << CautBin1(a, n, x) << "\n";
        else
            fout << CautBin2(a, n, x) << "\n";
    }
    return 0;
}