#include <iostream>
#include <fstream>

using namespace std;

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

int n, k, x, t, a[100001]; 	// t - type

int main(){
	int i, l, r, m, p;
	
	in >> n;
	
	for(i = 1; i <= n; i++)
		in >> a[i];
	
	in >> k;
	
	for(i = 0; i < k; i++){
		in >> t >> x;
		
		p = 0;
		l = 1, r = n;
		m = l + (l + r) / 2;
		
		if(t == 0){
			while(l <= r){
				if(a[m] == x && m > p){
					p = m;
					l = m + 1;
					m = (l + r) / 2;
				}
				else if(a[m] < x){
					l = m + 1;
					m = (l + r) / 2;
				}
				else{
					r = m - 1;
					m = (l + r) / 2;
				}
			}
			
			if(p == 0)
				out << "-1\n";
			else
				out << p << "\n";
		}
		
		if(t == 1){
			while(l <= r){
				if(a[m] <= x && m > p){
					p = m;
					l = m + 1;
					m = (l + r) / 2;
				}
				else if(a[m] > x){
					r = m - 1;
					m = (l + r) / 2;
				}
				else{
					l = m + 1;
					m = (l + r) / 2;
				}
			}
			out << p << "\n";
		}
		
		if(t == 2){
			p = n + 1;
		
			while(l <= r){
				if(a[m] >= x && m < p){
					p = m;
					r = m - 1;
					m = (l + r) / 2;
				}
				else if(a[m] < x){
					l = m + 1;
					m = (l + r) / 2;
				}
				else{
					r = m - 1;
					m = (l + r) / 2;
				}
			}
			out << p << "\n";
		}
	}
	
	return 0;
}