#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("cautbin.in");
ofstream g ("cautbin.out");
const int NMAX = 100001;
int v[NMAX], n;
int cautbin0 (int x)
{
    int p = 1, u = n, ans = -1;
    while (p <= u)
    {
        int mij = (p + u) / 2;
        if (v[mij] == x)
        {
            ans = mij;
            p = mij + 1;
        }
        else if (v[mij] < x)
        {
            p = mij + 1;
        }
        else if (v[mij] > x)
        {
            u = mij - 1;
        }
    }
    return ans;
}
int cautbin1(int x)
{
    /// 1 3
    /// 1 2 2 2 4
    int p = 1, u = n, ans;
    while (p <= u)
    {
        int mij = (p + u) / 2;
        if (v[mij] <= x)
        {
            ans = mij;
            p = mij + 1;
        }
        else if (v[mij] > x)
        {
            u = mij - 1;
        }
    }
    return ans;
}
int cautbin2(int x)
{
    /// 1 3
    /// 1 2 2 2 4
    int p = 1, u = n, ans;
    while (p <= u)
    {
        int mij = (p + u) / 2;
        if (v[mij] >= x)
        {
            ans = mij;
            u = mij - 1;
        }
        else if (v[mij] < x)
        {
            p = mij + 1;
        }
    }
    return ans;
}
int main()
{
    f >> n;
    for (int i = 1; i <= n; i++)
    {
        f >> v[i];
    }
    int q;
    f >> q;
    for (int i = 1; i <= q; i++)
    {
        int tip, x;
        f >> tip >> x;
        if (tip == 0)
        {
            g << cautbin0 (x) << '\n';
        }
        else if (tip == 1)
        {
            g << cautbin1 (x) << '\n';
        }
        else g << cautbin2 (x) << '\n';
    }
    return 0;
}