#include <fstream>
 
int nA[100010];
 
int absearch(int *arr, int l, int r, int x)
{
    if (l > r) {
        l -= 1; 
        if (arr[l] == x) {
            return l;
        } else {
            return -1;
		}
	}
    int m = (l + r) / 2;
    if (arr[m] > x) {
        return absearch(arr, l, m - 1, x);
	} else {
        return absearch(arr, m + 1, r, x);
	}
}
 
int bbsearch(int *arr, int l, int r, int x)
{
    if (l > r) {
        if (arr[l - 1] == x) {
            return l - 1;
        } else {
            return l;
		}
    int m = (l + r) / 2;
    if (arr[m] > x) {
        return bbsearch(arr, l, m - 1, x);
    } else {
        return bbsearch(arr, m + 1, r, x);
	}
}
 
int cbsearch(int *arr, int l, int r, int x)
{
    if (l > r) {
        return l;
	}
    m = (l + r) / 2;
    if (arr[m] >= x) {
        return cbsearch(arr, l, m - 1, x);
    } else {
        return cbsearch(arr, m + 1, r, x);
	}
}
 
int main(void)
{
    int nV, nM, a, b;
    std::ifstream in("cautbin.in");
    std::ofstream out("cautbin.out");
    in >> nV;
    for(int i(1); i <= nV; i++)
        in >> nA[i];
    in >> nM;
    for(int i(0); i < nM; i++)
    {
        in >> a >> b;
        if(a == 0) out << absearch(nA, 1, nV, b) << "\n";
        if(a == 1) out << bbsearch(nA, 1, nV, b) << "\n";
        if(a == 2) out << cbsearch(nA, 1, nV, b) << "\n";
    }
    return 0;
}