#include <fstream>
#define NMAX 100001

using namespace std;

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

int V[NMAX];
int n, m, Q, t;

int binarySearch(int st, int dr, int x) {
    if(st > dr) return -1;
    int mj = (st + dr) / 2;
    if(V[mj] == x) return max(mj, binarySearch(mj + 1, dr, x));
    if(V[mj] > x) return binarySearch(st, mj - 1, x);
    if(V[mj] < x) return binarySearch(mj + 1, dr, x);
}

int binaryMaxSearch(int st, int dr, int x) {
    int mj = (st + dr) / 2;
    if(st > dr) return -1;
    if(V[mj] <= x) return max(mj, binaryMaxSearch(mj + 1, dr, x));
    return binaryMaxSearch(st, mj - 1, x);
}

int binaryMinSearch(int st, int dr, int x) {
    int mj = (st + dr) / 2;
    if(st > dr) return NMAX + 1;
    if(V[mj] >= x) return min(mj, binaryMinSearch(st, mj - 1, x));
    return binaryMinSearch(mj + 1, dr, x);
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++) fin >> V[i];
    fin >> m;
    while(m--) {
        fin >> Q >> t;
        switch(Q){
            case 0: fout << binarySearch(1, n, t) << '\n';
                    break;
            case 1: fout << binaryMaxSearch(1, n, t) << '\n';
                    break;
            case 2: fout << binaryMinSearch(1, n, t) << '\n';
                    break;
        }
    }
    return 0;
}