#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
typedef long long ll;

string file="cautbin";

ifstream fin(file+".in");
ofstream fout(file+".out");

int n;
int a[NMAX];

int bs0(int x) {
    int st = 1, dr = n, ans = -1;
    while (st <= dr) {
        int m = (st + dr) >> 1;
        if (a[m] == x) {
            ans = m;
            st = m + 1;
        } else if (a[m] < x) st = m + 1;
        else dr = m - 1;
    }
    return ans;
}

int bs1(int x) {
    int st = 1, dr = n, ans = n;
    while (st <= dr) {
        int m = (st + dr) >> 1;
        if (a[m] <= x) {
            ans = m;
            st = m + 1;
        } else dr = m - 1;
    }
    return ans;
}

int bs2(int x) {
    int st = 1, dr = n, ans = 1;
    while (st <= dr) {
        int m = (st + dr) >> 1;
        if (a[m] >= x) {
            ans = m;
            dr = m - 1;
        } else st = m + 1;
    }
    return ans;
}

int main() {
    int x, type, t, i;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    fin >> t;
    while (t--) {
        fin >> type >> x;
        if (type == 0) fout << bs0(x);
        else if (type == 1) fout << bs1(x);
        else fout << bs2(x);
        fout << "\n";
    }
    return 0;
}