#include <fstream>
using namespace std;

int v[100002];

// Rendes binaris kereses
int bs(int st, int dr, int k)
{
    int lo, hi, mid;
    lo = st; hi = dr;
    while (lo <= hi)
    {
        mid = lo + (hi - lo) / 2;
        if (v[mid] == k) lo = hi + 1;
        else if (v[mid] < k) lo = mid + 1;
             else hi = mid - 1;
    }
    if (v[mid] == k) return mid;
    else return -1;
}

// 0: A legnagyobb pozicio, amelynek erteke X
int bs0(int st, int dr, int k)
{
    int lo, hi, mid;
    lo = st; hi = dr;
    while (lo <= hi)
    {
        mid = lo + (hi - lo) / 2;
        if (v[mid] <= k) lo = mid + 1;
        else hi = mid - 1;
    }
    mid = lo + (hi - lo) / 2;
    if (v[mid] > k) mid--;
    if (v[mid] == k) return mid;
    else return -1;
}

// 1: A legnagyobb pozicio, amelynek erteke kisebb vagy egyenlo mint X
int bs1(int st, int dr, int k)
{
    int lo, hi, mid;
    lo = st; hi = dr;
    while (lo < hi)
    {
        mid = lo + (hi - lo) / 2;
        if (v[mid] <= k) lo = mid + 1;
        else hi = mid;
    }
    mid = lo + (hi - lo) / 2;
    if (v[mid] > k) mid--;
    return mid;
}

// 2: A legkisebb pozicio, amelynek erteke nagyobb vagy egyenlo mint X
int bs2(int st, int dr, int k)
{
    int lo, hi, mid;
    lo = st; hi = dr;
    while (lo < hi)
    {
        mid = lo + (hi - lo) / 2;
        if (v[mid] < k) lo = mid + 1;
        else hi = mid;
    }
    mid = lo + (hi - lo) / 2;
    if (v[mid] < k) ++mid;
    return mid;
}

int main()
{
    ifstream fin("cautbin.in");
    ofstream fout("cautbin.out");
    int n, m, i, t, x;
    fin >> n;
    for (i=1; i<=n; i++)
    {
        fin >> v[i];
    }
    fin >> m;
    for (i=1; i<=m; i++)
    {
        fin >> t >> x;
        switch (t)
        {
            case 0: fout << bs0(1, n, x) << '\n'; break;
            case 1: fout << bs1(1, n, x) << '\n'; break;
            case 2: fout << bs2(1, n, x) << '\n'; break;
        }
    }
    fin.close();
    fout.close();
    return 0;
}