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

int n, m, v[100001], x;
short int intr;

int cautbin0 (int st, int dr, int cautat) {
    int mid = (st+dr)/2;

    while (st<=dr) {

        mid = (st+dr)/2;
        if (v[mid] < x) {
            st = mid+1;
        } else if (v[mid] > x) {
            dr = mid-1;
        } else {
            //valpoz = mid;
            st = mid+1;
        }
    }
    mid = (st+dr)/2;

    if (v[mid] > cautat) {
        mid--;
    }
    if (v[mid] == cautat) {
        return mid;
    }

    return -1;
}

int cautbin1 (int st, int dr, int cautat) {

    int mid = (st+dr)/2;

    while (st < dr) {
        int mid = (st+dr)/2;

        if (v[mid] > x) {
            dr = mid;
        } else {
            st = mid+1;
        }
    }

    mid = (st+dr)/2;

    if (v[mid] > cautat) {
        mid--;
    }

    return mid;
}

int cautbin2 (int st, int dr, int cautat) {

    int mid = (st+dr)/2;

    while (st<dr) {
        int mid = (st+dr)/2;

        if (v[mid] < x) {
            st = mid+1;
        } else {
            dr = mid;
        }
    }

    mid = (st+dr)/2;

    if (v[mid] < cautat) {
        mid++;
    }

    return mid;
}

int main() {

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

    fin >> n;

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

    fin >> m;

    for (int nrintrebare = 1; nrintrebare<=m; nrintrebare++) {
        fin >> intr >> x;

        if (intr == 0) {
            fout << cautbin0(1, n, x) << endl;
        }

        if (intr == 1) {
            fout << cautbin1(1, n, x) << endl;
        }

        if (intr == 2) {
            fout << cautbin2(1, n, x);
        }

    }


    fin.close();
    fout.close();

    return 0;
}