#include <iostream>
#include <fstream>

using namespace std;

int N, sir[100000], M;

int binarySearch(int x) {
    int st = 0, dr = N - 1;
    int last, mid;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(sir[mid] <= x){
            st = mid + 1;
            last = mid;
        } else dr = mid - 1;
    }
    if(sir[last] == x)
        return last + 1;
    else
        return -1;
}

int binarySearch1(int x) {
    int st = 0, dr = N - 1;
    int last, mid;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(sir[mid] <= x){
            st = mid + 1;
            last = mid;
        } else dr = mid - 1;
    }
    return last + 1;
}

int binarySearch2(int x) {
    int st = 0, dr = N - 1;
    int last, mid;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(sir[mid] <= x && sir[mid-1] != x){
            st = mid + 1;
            last = mid;
        } else dr = mid - 1;
    }
    if(sir[last] == x)
        return last + 1;
    else
        return last;
}

int main()
{
    ifstream in("cautbin.in");
    ofstream out("cautbin.out");

    in >> N;

    for(int i = 0; i < N; i++) {
        in >> sir[i];
    }

    in >> M;

    for(int j = 0; j < M; j++) {
        int tip, x;
        in >> tip >> x;
        switch(tip) {
        case 0:
            out << binarySearch(x) << endl;
            break;
        case 1:
            out << binarySearch1(x) << endl;
            break;
        case 2:
            out << binarySearch2(x) << endl;
            break;
        }
    }

    return 0;
}