#include <iostream>
#include <fstream>
#define nmax 100005
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int n, m;
int A[nmax];

int op0(int x) {
    int hi = n, lo = 1, mid;
    bool ok = false;
    while (lo <= hi) {
        mid = (hi + lo) >> 1;
        if (A[mid] == x) {
            lo = mid+1;
            ok = true;
            continue;
        }
        if (A[mid] > x)
            hi = mid - 1;
        else
            lo = mid + 1;
    }
    if (!ok)
        hi = -1;
    return hi;
}

int op1(int x) {
    int hi = n, lo = 1, mid;
    while (lo <= hi) {
        mid = (hi + lo) >> 1;
        if (A[mid] <= x) {
            lo = mid + 1;
        } else
            hi = mid - 1;
    }
    return hi;
}

int op2(int x) {
    int hi = n, lo = 1, mid;
    while (lo <= hi) {
        mid = (hi + lo) >> 1;
        if (A[mid] >= x)
            hi = mid - 1;
        else
            lo = mid + 1;
    }
    return lo;
}

void readData() {
    int i;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> A[i];
}

void solve() {
    int i, x, op;
    fin >> m;
    for (i = 1; i <= m; i++) {
        fin >> op >> x;
        if (op == 0)
            fout << op0(x) << "\n";
        else if (op == 1)
            fout << op1(x) << "\n";
        else
            fout << op2(x) << "\n";
            
    }
}


int main() {
    readData();
    solve();
    fin.close();
    fout.close();
    return 0;
}