#include <fstream>
#include <stack>
#include <algorithm>

using namespace std;

const int NMAX = 1e5 + 5;

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

int v[NMAX];

int op0(int x, int n, int p)
{
    int curr = 1;
    for( ; p > 0; p = p >> 1) {
        if(curr + p <= n && v[curr + p] <= x) {
            curr += p;
        }
    }
    if(v[curr] != x)
        curr = -1;
    return curr;
}

int op1(int x, int n, int p)
{
    int curr = 1;
    for( ; p > 0; p = p >> 1) {
        if(curr + p <= n && v[curr + p] <= x) {
            curr += p;
        }
    }
    return curr;
}

int op2(int x, int n, int p)
{
    int curr = n;
    for( ; p > 0; p = p >> 1) {
        if(curr - p > 0 && v[curr - p] >= x) {
            curr -= p;
        }
    }
    return curr;
}

int main()
{
    int n, m;
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> v[i];
    }
    int p =1;
    for(; p <= n; p = p << 1);
    p = p >> 1;
    cin >> m;
    for(int i = 1; i <= m; ++i) {
        int type, x;
        cin >> type >> x;
        if(type == 0) {
            cout << op0(x, n, p) << "\n";
        }
        if(type == 1) {
            cout << op1(x, n, p) << "\n";
        }
        if(type == 2) {
            cout << op2(x, n, p) << "\n";
        }
    }
    return 0;
}