#include <fstream>

using namespace std;

ifstream cin ("cautbin.in");
ofstream cout ("cautbin.out");

const int NMAX = 100004;

int elements [NMAX];

int main() {
    int numberOfElements;
    cin >> numberOfElements;
    for (int indexOfElement = 1; indexOfElement <= numberOfElements; ++ indexOfElement)
        cin >> elements[indexOfElement];

    int numberOfQueries;
    cin >> numberOfQueries;

    for (int query = 1; query <= numberOfQueries; ++ query)
    {
        int queryType, queryValue;
        cin >> queryType >> queryValue;

        if (queryType == 0)
        {
            int _left = 1;
            int _right = numberOfElements;
            int solution = 1;

            while (_left <= _right) {
                int middle = (_left + _right) / 2;

                if (elements[middle] <= queryValue) {
                    _left = middle + 1;
                    solution = middle;
                } else
                    _right = middle - 1;
            }
            if (elements[solution] == queryValue)
                cout << solution << '\n';
            else cout << -1 << '\n';
        }
        else if (queryType == 1)
        {
            int _left = 1;
            int _right = numberOfElements;
            int solution;

            while (_left <= _right) {
                int middle = (_left + _right) / 2;

                if (elements[middle] <= queryValue) {
                    _left = middle + 1;
                    solution = middle;
                } else
                    _right = middle - 1;
            }
            cout << solution << '\n';
        }
        else if (queryType == 2)
        {
            int _left = 1;
            int _right = numberOfElements;
            int solution;

            while (_left <= _right) {
                int middle = (_left + _right) / 2;

                if (queryValue <= elements [middle])
                {
                    _right = middle - 1;
                    solution = middle;
                }
                else _left = middle + 1;
            }
            cout << solution << '\n';
        }
    }
    return 0;
}