#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) / 2;
                    if (a[mid] > x)
                        right = mid - 1;
                    else
                        left = mid + 1;
            }
            fout << mid << endl;
        }
        if (intrebare == 1){
            while (left < right){
                mid = (left + right) / 2;
                if (a[mid] <= x)
                    left = mid + 1;
                else
                    right = mid;
            }
            raspuns = left - 1;
            fout << raspuns << endl;
        }
        if (intrebare == 2){
            while (left < right){
                mid = (left + right) / 2;
                if (a[mid] < x)
                    left = mid + 1;
                else
                    right = mid;
            }
            raspuns = left;
            fout << raspuns << endl;
        }
    }
    return 0;
}