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

using namespace std;

class Solution {
    private:
	int n, m;
	vector<int> numbers;

	int cautbin(int question_type, int target){
	    int left = 1, right = n;
	    int best = -1;

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

		switch (question_type) {
			case 0:
			    if(numbers[mij] == target){
				best = mij;
				left = mij + 1;
			    }
			    else if(numbers[mij] > target)
				right = mij - 1;
			    else 
				left = mij + 1;
			    break;
			case 1:
			    if(numbers[mij] <= target){
				best = mij;
				left = mij + 1;
			    } else {
				right = mij - 1;
			    }
			    break;
			case 2:
			    if(numbers[mij] >= target){
				best = mij;
				right = mij - 1;
			    } else {
				left = mij + 1;
			    }
			    break;
			default:
				break;
		}
	    }

	    return best;
	}

    public:
	void solve(){
	    ifstream fin("cautbin.in");
	    ofstream fout("cautbin.out");

	    fin >> n;
	    numbers.resize(n + 1);

	    for(int i = 1; i <= n; i++)
		fin >> numbers[i];

	    fin >> m;
	    int type, target;	
	    for(int i = 0; i < m; i++){
		fin >> type >> target;
		fout << cautbin(type, target) << '\n';
	    }
	}
};


int main(){
    Solution *sol = new Solution();
    sol->solve();
    return 0;
}