#include <bits/stdc++.h>
using namespace std;

/**                                     d  s
a = 1 3 4 8 8 8 10 20 25 25 30 50 50 50 50 70 90
                                         m
x = 50
p = 15

1. Dat un x, sa se afle o pozitie a lui x in a, sau -1 daca
   x nu este in a
2. Dat x, sa se determine cea mai din dreapta pozitie p
   in care a[p] <= x
3. Dat x, sa se determine cea mai din stanga pozitie p
   in care x <= a[p]
*/

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int a[100005], n;

/// cauta cea mai din dreapta pozitie p cu a[p]=x
/// sau -1 daca x nu apare in a
int CautBin0(int x)
{
    int st, dr, mij, p;
    st = 1; dr = n; p = -1;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (a[mij] == x)
        {
            p = mij;
            st = mij + 1;
        }
        else if (a[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }
    return p;
}

/// cea mai din dreapta pozitie p in care a[p] <= x
int CautBin1(int x)
{
    int st, dr, mij, p;
    st = 1; dr = n; p = -1;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (a[mij] <= x)
        {
            p = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return p;
}

/// cea mai din stanga pozitie p in care x <= a[p]
int CautBin2(int x)
{
    int st, dr, mij, p;
    st = 1; dr = n; p = -1;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (x <= a[mij])
        {
            p = mij;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    return p;
}

int main()
{
    int i, m, op, x;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];

    fin >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> op >> x;
        if (op == 0) fout << CautBin0(x) << "\n";
        else if (op == 1) fout << CautBin1(x) << "\n";
        else fout << CautBin2(x) << "\n";
    }

    fout.close();
    fin.close();
    return 0;
}