#include <fstream>

using namespace std;

ifstream cin("cautbin.in");
ofstream cout("cautbin.out");

const int N = 100000;
int v[N], n;

int caut_0(int x){
    int st = 0, dr = n - 1, rez = -1;
    while (st <= dr){
        int m = (st + dr) / 2;
        if (v[m] <= x)
        {
            rez = m;
            st = m + 1;
        }
        else
            dr = m - 1;
    }
    if (rez == -1 || v[rez] < x)
        return -1;
    return rez + 1;
}

int caut_1(int x){
    int st = 0, dr = n - 1, rez = -1;
    while (st <= dr)
    {
        int m = (st + dr) / 2;
        if (v[m] <= x)
        {
            rez = m;
            st = m + 1;
        }
        else
            dr = m - 1;
    }
    return rez + 1;
}

int caut_2(int x){
    int st = 0, dr = n - 1, rez = -1;
    while (st <= dr)
    {
        int m = (st + dr) / 2;
        if (v[m] >= x)
        {
            rez = m;
            dr = m - 1;
        }
        else
            st = m + 1;
    }
    return rez + 1;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> v[i];
    int m;
    cin >> m;
    for (int i = 0; i < m; i++){
        int c, x;
        cin >> c >> x;
        if (c == 0)
            cout << caut_0(x) << "\n";
        else if (c == 1)
            cout << caut_1(x) << "\n";
        else
            cout << caut_2(x) << "\n";
    }
    return 0;
}