#include <bits/stdc++.h>
using namespace std;

ifstream f("input.in");
ofstream g("output.out");

int c0(const vector<int> &v, int start, int end, int val) {
    int poz = -2;
    while(start <= end) {
        int mid = (start + end) / 2;
        if(v[mid] == val) {
            poz = mid;
            start = mid + 1;
        }
        else if(v[mid] > val) {
            end = mid - 1;
        }
        else start = mid + 1;
    }
    return poz + 1;
}

int c1(vector<int> &v, int start, int end, int val) {
    int poz = -2;
    while(start <= end) {
        int mid = (start + end) / 2;
        if(v[mid] <= val) {
            poz = mid;
            start = mid + 1;
        }
        else end = mid - 1;
    }
    return poz + 1;
}

int c2(vector<int> &v, int start, int end, int val) {
    int poz = -2;
    while(start <= end) {
        int mid = (start + end) / 2;
        if(v[mid] >= val) {
            poz = mid;
            end = mid - 1;
        }
        else start = mid + 1;
    }
    return poz + 1;
}

int main() {
    int n, m;
    vector<int> v;
    f >> n;
    for(int i = 0; i < n; i++) {
        int a;
        f >> a;
        v.push_back(a);
    }
    f >> m;
    while(m--) {
        int ask, x;
        f >> ask >> x;
        if(ask == 0)
            g << c0(v, 0, n - 1, x) << '\n';
        if(ask == 1)
            g << c1(v, 0, n - 1, x) << '\n';
        if(ask == 2)
            g << c2(v, 0, n - 1, x) << '\n';
        
    }
    return 0;
}