#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;


class Problem {
 public: 
 	void solve(){
 		read_input();
 		print_output(get_result());
 	}
 private:
 	int n, m;
 	vector<int> v;
 	vector<pair <int, int> > obtain;

 	void read_input(){
 		ifstream fin("cautbin.in");
 		fin >> n;
 		v.push_back(-1);
 		for(int i = 1, x; i <= n; i++) {
 			fin >> x;
 			v.push_back(x);
 		}
 		v.push_back(-1);
 		fin >> m;
 		for(int i = 0, x, y; i < m; i++) {
 			fin >> x >> y;
 			obtain.push_back(make_pair(x, y));
 		}
 		fin.close();
 	}
 	int normal_binary_search(vector<int> arr, int left, int right, int elem) {

 		if(right >= left) {
 			int middle = left + (right - left)/2;
 			if(arr[middle] == elem) {
 				return middle;
 			}
 			else if(arr[middle] > elem)
 				return normal_binary_search(arr, left, middle - 1, elem);
			else return normal_binary_search(arr, middle + 1, right, elem);

 		}
 		return -1;
 	}
 	int binary_search(vector<int> arr, int left, int right, int elem) {

 		if(right >= left) {
 			int middle = left + (right - left)/2;
 			if(right - left == 1) {
 				return left;
 			}
 			else if(arr[middle] > elem)
 				return binary_search(arr, left, middle - 1, elem);
			else return binary_search(arr, middle + 1, right, elem);

 		}
 		return -1;
 	}
 	vector<int> get_result() {
 		vector<int> result;

 		for(int i = 0; i < m; i++){
 			if (obtain[i].first == 0) { //
 				int pos = normal_binary_search(v, 1, n, obtain[i].second);
 				result.push_back(pos);
 			}
 			else if (obtain[i].first == 1) {
 				int pos = binary_search(v, 1, n, obtain[i].second);
 				if(v[pos] > obtain[i].second){
 					while(v[pos] > obtain[i].second){
 						pos--;
 					}
 				}
 				while(v[pos] <= obtain[i].second && pos <= n){
 					pos++;
 				}
 				if(pos > 1) pos--;
 				result.push_back(pos);
 			}
 			else if (obtain[i].first == 2){
 				int pos = binary_search(v, 1, n, obtain[i].second);
 				if(v[pos] < obtain[i].second){
 					while(v[pos] < obtain[i].second){
 						pos++;
 					}
 				}
 				while(v[pos] >= obtain[i].second && pos >= 1){
 					pos--;
 				}
 				if(pos < n) pos++;
 				result.push_back(pos);
 			}
 		}
 		return result;
 	}
 	void print_output(vector<int> result) {
		ofstream fout("cautbin.out");
		for(int i = 0; i < m; i++){
			fout << result[i] << "\n";
		}
		fout.close();
	}

};

int main() {
	Problem pb;
	pb.solve();
	return 0;
}