#include <fstream>
#include <string>
#include <vector>

using namespace std;


string const inFile = "cautbin.in";
string const outFile = "cautbin.out";


ifstream Read(inFile);
ofstream Write(outFile);


void ReadVec(vector<unsigned> &vec) {
    unsigned n;
    Read >> n;

    vec.resize(n);

    for (unsigned i = 0; i < n; ++i) {
        Read >> vec[i];
    }
}


int BinarySearch(
    vector<unsigned> const &vec,
    unsigned const left,
    unsigned const right,
    unsigned const value,
    unsigned const type)
{
    if (left > right) {
        if (type == 0) {
            return vec[right] == value ? right : -2;
        }
        if (type == 1) {
            return right;
        }
        if (type == 2) {
            return left;
        }
    }

    unsigned mid = (left + right) >> 1;

    if (type == 0) {
        if (vec[mid] <= value) {
            return BinarySearch(vec, mid + 1, right, value, type);
        }

        return BinarySearch(vec, left, mid - 1, value, type);
    }

    if (type == 1) {
        if (vec[mid] <= value) {
            return BinarySearch(vec, mid + 1, right, value, type);
        }

        return BinarySearch(vec, left, mid - 1, value, type);
    }

    if (vec[mid] >= value) {
        return BinarySearch(vec, left, mid - 1, value, type);
    }

    return BinarySearch(vec, mid + 1, right, value, type);
}


int main() {
    vector<unsigned> vec;

    ReadVec(vec);

    unsigned m;
    unsigned type;
    unsigned value;
    int result;

    Read >> m;

    while (m--) {
        Read >> type;
        Read >> value;

        result = BinarySearch(vec, 0, vec.size() - 1, value, type);

        if (result == -1) {
            Write << "-1\n";
        }
        else {
            Write << result + 1 << '\n';
        }
    }

    return 0;
}