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

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

int sir[100001];

int cautareBinara(int x, int st, int dr) {
    if (st >= dr) {
        return st;
    }
    int mij = (st + dr) / 2;
    if (sir[mij] == x) {
        return mij;
    } else if (sir[mij] > x) {
        return cautareBinara(x, st, mij);
    } else {
        return cautareBinara(x, mij+1, dr);
    }
}

int main()
{
    int n;
    fin >> n;
    for (int i = 0; i < n; ++i) {
        fin >> sir[i];
    }
    int query;
    fin >> query;
    for (int i = 0; i < query; ++i) {
        int dir, x;
        fin >> dir >> x;
        int posX = (cautareBinara(x, 0, n-1));
        if (dir == 0) {
            if (sir[posX] == x) {
                for (int i = posX; sir[i] == x && i < n; ++i) {
                    posX = i;
                }
                fout << posX + 1;
            } else {
                fout << - 1;
            }
        } else if (dir == 1) {
            for (int i = posX - 1; sir[i] <= x && i < n; ++i){
                posX = i;
            }
            fout << posX + 1;
        } else {
            for (int i = posX; sir[i] >= x && i < n; --i) {
                posX = i;
            }
            fout << posX + 1;
        }
        fout << '\n';
    }
}
/*https://infoarena.ro/problema/cautbin
idee
citim sirul
Algoritm de cautare binara :
    avem st si dr, gasim mij st + dr /2
    daca am gasit elementul pe mijloc ne oprim, daca e mai mare facem binSearch pe st mij -1, daca e mai mic, mij, dr

2 4 5
3
*/