#include <iostream>
#define NMAX 100001
using namespace std;

int v[NMAX], n, i, Q, x, cer;

int caut0(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 caut1(int x)
{
    int p = 1, u = n, poz = -1;
    while(p <= u)
    {
        int m = (p + u) / 2;
        if(x >= v[m])
        {
            p = m + 1;
            poz = m;
        }
        else u = m - 1;
    }
    return poz;
}

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

int main()
{
    cin >> n;
    for(i = 1; i <= n; i++)
        cin >> v[i];
    cin >> Q;
    while(Q--)
    {
        cin >> cer >> x;
        if(cer == 0)
        {
            cout << caut0(x) << '\n';
        }
        else if(cer == 1)
        {
            cout << caut1(x) << '\n';
        }
        else
        {
            cout << caut2(x) << '\n';
        }
    }
    return 0;
}