#include <iostream>
#include <fstream>
using namespace std;

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

int n, v[100001];

int cautbin0(int x)
{
    int p = 1, u = n, poz = -1;
    while(p <= u)
        {
            int m = (p + u) / 2;
            if(x == v[m])
                poz = m;
            if(x >= v[m])
                p = m + 1;
            else
                u = m - 1;
        }
    return poz;
}

int cautbin1(int x)
{
    int p = 1, u = n, poz = -1;
    while(p <= u)
        {
            int m = (p + u) / 2;
            if(x >= v[m])
                {
                    poz = m;
                    p = m + 1;
                }
            else
                u = m - 1;
        }
    return poz;
}

int cautbin2(int x)
{
    int p = 1, u = n, poz = -1;
    while(p <= u)
        {
            int m = (p + u) / 2;
            if(x <= v[m])
                {
                    poz = m;
                    u = m - 1;
                }
            else
                p = m + 1;
        }
    return poz;
}

int main()
{
    int m, t, x;
    in >> n;
    for(int i = 1; i <= n; i++)
        in >> v[i];
    in >> m;
    for(int i = 1 ; i <= m; i++)
        {
            in >> t >> x;
            switch(t)
                {
                case 0:
                    out << cautbin0(x) << endl;
                    break;
                case 1:
                    out << cautbin1(x) << endl;
                    break;
                case 2:
                    out << cautbin2(x) << endl;
                    //break;
                }
        }
    return 0;
}