#include <iostream>

using namespace std;
const int NMAX = 1e5 + 2; // => LOGMAX = 16
const int LOGMAX = 16;
// 1e5 = 100'000
// 1e6 = 1'000'000

int a[NMAX];
int n;

int cerinta_0 (int x)
{
    int index = 0;
    for (int bit = LOGMAX; bit >= 0; bit--)
    {
        index += (1 << bit);
        if (index > n || a[index] > x) index -= (1 << bit);
    }

    if (a[index] == x) 
        return index;
    else return -1;
}

int cerinta_1 (int x)
{
    int index = 0;
    for (int bit = LOGMAX; bit >= 0; bit--)
    {
        index += (1 << bit);
        if (index > n || a[index] > x) index -= (1 << bit);
        // (1 << bit) raamane activ
        // (index <= n && a[index] <= x)
    }
    return index;
}

int cerinta_2 (int x)
{
    int index = 0;
    for (int bit = LOGMAX; bit >= 0; bit--)
    {
        index += (1 << bit);
        if (index > n || a[index] >= x) index -= (1 << bit);
    }
    return index + 1;
}

int main ()
{
    freopen("cautbin.in" , "r" , stdin);
    freopen("cautbin.out" , "w" , stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int m; cin >> m;
    while (m--) // for (int i = 1; i <= m; i++)
    {
        int c; cin >> c;
        int x; cin >> x;
        if (c == 0) cout << cerinta_0(x) << '\n';
        if (c == 1) cout << cerinta_1(x) << '\n';
        if (c == 2) cout << cerinta_2(x) << '\n';
    }
}