#include <fstream>
using namespace std;
ifstream is ("cautbin.in");
ofstream os ("cautbin.out");

int n, v[100003], k, x, y, m, s, d, nr;
int C0 (int i, int y);
int C1 (int i, int y);
int C2 (int i, int y);

int main()
{
    is >> n;
    for(int i = 1; i <= n; ++i)
        is >> v[i];
    is >> k;
    for(int i = 1; i <= k; ++i)
    {
        is >> x >> y;
        if (x == 0) os << C0(1, y) << '\n';
        if (x == 1) os << C1(1, y) << '\n';
        if (x == 2) os << C2(1, y) << '\n';
    }
    is.close();
    os.close();
    return 0;
}
int C0 (int s, int y)
{
    nr = -1;
    d = n;
    s = 1;
    while(s <= d)
    {
        m =(s+d)/2;
        if (v[m] == y)
        {
            nr = m;
            s = m + 1;
        }
        if(v[m] > y)
            d = m - 1;
        else
            s = m + 1;
    }
    return nr;
}
int C1 (int s, int y)
{
    nr = -1;
    d = n;
    s = 1;
    while(s <= d)
    {
        m =(s+d)/2;
        if(v[m]<=y)
        {
            nr = m;
            s= m + 1;
        }
        else
            d = m - 1;
    }
    return nr;
}
int C2 (int s, int y)
{
    nr = -1;
    d = n;
    s = 1;
    while(s <= d)
    {
        m =(s + d)/2;
        if(v[m] >= y)
        {
            nr = m;
            d = m - 1;
        }
        else s = m + 1;
    }
    return nr;
}