#include <fstream>

#define Nmax 100100

using namespace std;

int logN, N, M, A[Nmax];

int binarySearch(int Value) {

    int left, right, middle;

    left = 1;
    right = N;

    while(left < right) {

        middle = (left + right) >> 1;

        if(A[middle] <= Value)
            left = middle + 1;
        else
            right = middle;
    }

    return left;

}
void Read(ifstream & in) {

    in >> N;

    for(int i = 1; i <= N; i++)
        in >> A[i];

    in >> M;

}
int main() {

    int x, index, type;
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");

    Read(in);

    while(M--) {

        in >> type >> x;

        x -= (type == 2 ? 1 : 0);

        switch(type) {

            case 0:
                index = binarySearch(x);
                out << (A[index - 1] == x ? (index - 1) : -1);
                break;

            case 1:
                index = binarySearch(x);
                out << (index - 1);
                break;

            case 2:
                index = binarySearch(x-1);
                out << index;
                }

        out << '\n';

        }

    in.close();
    out.close();

    return 0;
}