#include <iostream>
#include <fstream>
using namespace std;

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

int n;
int v[100001];
int q;
int c, num;

int BS (int x) {
    int st = 1, dr = n, mij, rez = -1;
    while (st <= dr) {
        mij = (dr+st)/2;
        if (v[mij] == x) {
            rez = mij;
            st = mij+1;
        }
        else {
            if (v[mij] < x)
                st = mij+1;
            else
                dr = mij-1;
        }
    }
    return rez;
}

int BS1 (int x) {
    int st = 1, dr = n, mij, rez = -1;
    while (st <= dr) {
        mij = (st+dr)/2;
        if (v[mij] <= x) {
            rez = mij;
            st = mij+1;
        }
        else
            dr = mij-1;
    }
    return rez;
}

int BS2 (int x) {
    int st = 1, dr = n, mij, rez = -1;
    while (st <= dr ) {
        mij = (st+dr)/2;
        if (v[mij] >= x) {
            rez = mij;
            dr = mij-1;
        }
        else
            st = mij+1;
    }
    return rez;
}

int main() {
    in >> n;
    for (int i=1; i<=n; ++i)
        in >> v[i];

    in >> q;
    for (int i=1; i<=q; ++i) {
        in >> c >> num;
        if (c == 0)
            out << BS(num) << "\n";
        else {
            if (c == 1)
                out << BS1(num) << "\n";
            else
                out << BS2(num) << "\n";
        }
    }

    in.close();
    out.close();
    return 0;
}