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

char filename[] = "cautbin.in";

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(filename);
 		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 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 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 = binary_search(v, 1, n, obtain[i].second);
 				while (v[pos] == v[pos + 1]){
 					pos = pos + 1;
 				}
 				result.push_back(pos);
 			}
 			else if (obtain[i].first == 1) {
 				int pos = binary_search(v, 1, n, obtain[i].second);
 				// while (v[pos] == v[pos - 1]){
 				// 	pos = pos - 1;
 				// }
 				pos = pos - 1;
 				result.push_back(pos);
 			}
 			else if (obtain[i].first == 2){
 				int pos = binary_search(v, 1, n, obtain[i].second);
 				// while (v[pos] == v[pos + 1]){
 				// 	pos = pos + 1;
 				// }
 				pos = pos + 1;
 				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;
}