#include <fstream>
using namespace std;

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

    long long int N;
    fin >> N;
    long long int i, a[100001];
    for (i = 1; i <= N; ++i)
        fin >> a[i];
    long long int M;
    fin >> M;
    for (i = 1; i <= M; ++i){
        long long int intrebare, x;
        fin >> intrebare >> x;
        long long int left = 1, right = N, mid;
        long long int raspuns = -1;
        if (intrebare == 0){
            while (left <= right){
                mid = left + (right - left) / 2;
                if (a[mid] <= x){
                    left = mid + 1;
                }
                else{
                    right = mid - 1;
                }
            }
            mid = left + (right - left) / 2;
            if (a[mid] > x)
                --mid;
            if (a[mid] == x)
                raspuns = mid;
            fout << raspuns << endl;
        }
        if (intrebare == 1){
            while (left < right){
                mid = left + (right - left) / 2;
                if (a[mid] <= x){
                    left = mid + 1;
                }
                else
                    right = mid;
            }
            mid = left + (right - left) / 2;
            if (a[mid] > x)
                --mid;
            raspuns = mid;
            fout << raspuns << endl;
        }
        if (intrebare == 2){
            while (left < right){
                mid = (left + right) / 2;
                if (a[mid] >= x){
                    right = mid;
                }
                else
                    left = mid + 1;
            }
            mid = left + (right - left) / 2;
            if (a[mid] < x)
                ++mid;
            raspuns = mid;
            fout << raspuns << endl;
        }
    }
    return 0;
}