#include <fstream>
#include <vector>

using namespace std;

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

vector<long long> elements;

int lowerBound(int left, int right, long long value);
int upperBound(int left, int right, long long value);

int main(){

    int arraySize, queryCount;
    
    fin >> arraySize;
    elements.resize(arraySize);

    for(int i = 0; i < arraySize; i++)
        fin >> elements[i];
    
    fin >> queryCount;

    for(long long i = 0, queryType, queryValue; i < queryCount; i++){
        fin >> queryType >> queryValue;

        int indexFound;

        if(queryType == 0){
            indexFound = upperBound(0, elements.size() - 1, queryValue);

            if(elements[indexFound - 1] == queryValue)
                fout << indexFound << '\n';
            else
                fout << "-1\n";
        }else if(queryType == 1){
            indexFound = upperBound(0, elements.size() - 1, queryValue);

            fout << indexFound << '\n';
        }else{
            indexFound = lowerBound(0, elements.size() - 1, queryValue);

            fout << indexFound + 1 << '\n';
        }
    }

    return 0;
}

int lowerBound(int left, int right, long long value){
    int middle, indexFound = elements.size();

    while(left <= right){
        middle = (left + right) / 2;

        if(value <= elements[middle]){
            indexFound = middle;
            right = middle - 1;
        }else{
            left = middle + 1;
        }
    }

    return indexFound;
}

int upperBound(int left, int right, long long value){
    int middle, indexFound = elements.size();

    while(left <= right){
        middle = (left + right) / 2;

        if(value < elements[middle]){
            indexFound = middle;
            right = middle - 1;
        }else{
            left = middle + 1;
        }
    }

    return indexFound;
}