#include <fstream>

using namespace std;

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

int n, v[100001];

// cea mai mare pozitie pe care se afla un elem cu valoare x sau -1
void case0(int val)
{
    int pos = 0;
    for (int bit = 17; bit >= 0; bit--)
    {
        int nextpos = pos + (1 << bit);
        if (nextpos <= n && v[nextpos] <= val)
            pos = nextpos;
    }
    if (v[pos] == val)
        cout << pos << '\n';
    else
        cout << -1 << '\n';
}

// cea mai mare pozitie pe care se afla un elem mai mic / egal cu x
void case1(int val)
{
    int pos = 0;
    for (int bit = 17; bit >= 0; bit--)
    {
        int nextpos = pos + (1 << bit);
        if (nextpos <= n && v[nextpos] <= val)
            pos = nextpos;
    }
    cout << pos << '\n';
}

// cea mai mica pozitie pe care se afla un elem mai mare / egal cu x
void case2(int val)
{
    int pos = n;
    for (int bit = 17; bit >= 0; bit--)
    {
        int nextpos = pos - (1 << bit);
        if (nextpos >= 1 && v[nextpos] >= val)
            pos = nextpos;
    }
    cout << pos << '\n';
}

// o rezolv cu cautarea binara a lui patrascu
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> v[i];
    int m; cin >> m;
    while (m--)
    {
        int t, val;
        cin >> t >> val;
        if (t == 0)
            case0(val);
        else if (t == 1)
            case1(val);
        else if (t == 2)
            case2(val);
    }
    return 0;
}