#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;


// 0 x - biggest position for element with value x or -1 if we can't find it
// 1 x biggest posisition for element with value <= x. It is guaranteed that smallest number <= x
// 2 x smallest position for element with value >= x. it is guaranteed that biggest number is >= x

int binary_seach_(vector<int> values, int left, int right, int searched_value, int search_type) {

    int best_index = -2;
    
    while(left <= right) {
        // cout << "Eu sunt best_index: " << best_index << "\n";

        int mid = left + (right - left) / 2;
        // cout << "Eu sunt mid: " << mid << "\n";
        
        switch(search_type) {
            case 0: 
                if (values[mid] == searched_value) {
                    best_index = mid;
                    left = mid + 1;
                    continue;
                }
                break;
            case 1:
                if(values[mid] <= searched_value) {
                    best_index = mid;
                    left = mid + 1;
                    continue;
                }
                break;
            case 2:
                if(values[mid] >= searched_value) {
                    best_index = mid;
                    right = mid - 1;
                    continue;
                }
                break;
            default:
                cout << "You shouldn't be here!\n";
                exit(1);
        }

        if ( values[mid] < searched_value) {
            left = mid + 1;
        }

        if ( values[mid] > searched_value) {
            right = mid - 1;
        }
    }

    //If we cannot find any value, we return -1
    // cout << "Before Returning best_index: " << best_index << "\n";
    return best_index + 1;
}

int main() {

    int N, M;
    vector<int> values;

    // N - number of elements
    // M - number of questions (0 x     1x      2 x)

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

    in >> N;
    while(N--) {
        int tmp;
        in >> tmp;
        values.push_back(tmp);
    }

    in >> M;
    while(M--) {
        int choice, x;
        in >> choice >> x;

        int val = binary_seach_(values, 0, values.size() - 1, x, choice);
        // cout << val << "\n";
        out << val << "\n";
    }
    
    out.close();
    in.close();
    return 0;
}