#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int s[100000];
int n,m,t,x, i;

int cb(int a, int b, int x){
	int m;
	while(a <= b) {
		m = (b+a)/2;
		if(s[m] == x){
			if (t==0 || t == 1){
				i = 0;
				while(s[m+i] == x){
					i++;
				}
				return m+i-1;
			} else {
				i = 0;
				while(s[m-i] == x){
					i++;
				}
				return m-i+1;
			}
		}
		if(s[m] > x){
			b = m-1;
		} else {
			a = m+1;
		}
	}
	if (t == 0)
		return -1;
	if (t == 1) return b;
	return a;
}
int main() {
	fin >> n;
	for(int i=0; i<n; i++) fin >> s[i];
	fin >> m;
	
	for(int i = 0; i<m; i++){
		fin >> t >> x;
		fout << cb(0, n-1, x)<<'\n';
	}
}