#include <bits/stdc++.h>
 
using namespace std;
 
ifstream f("cautbin.in");
ofstream g("cautbin.out");

int a[100001];
int N, Q, q, x;

int UpperBound1(int x){
	int l = 1, r = N;
	while(l <= r){
		int m = (l + r) >> 1;
		if(a[m] > x) r = m - 1;
		else l = m + 1;
	}

	return (a[r] == x)? r : -1;
}

int UpperBound2(int x){
	int l = 1, r = N;
	while(l <= r){
		int m = (l + r) >> 1;
		if(a[m] > x) r = m - 1;
		else l = m + 1;
	}

	return r;
}

int LowerBound(int x){
	int l = 1, r = N;
	while(l <= r){
		int m = (l + r) >> 1;
		if(a[m] < x) l = m + 1;
		else r = m - 1;
	}

	return l;
}


int main(){
	f >> N;
	for(int i = 1;i <= N;i++)
		f >> a[i];
	a[0] = -1;
	f >> Q;
	while(Q--){
		f >> q >> x;
		if(q == 0) g << UpperBound1(x) << "\n";
		if(q == 1) g << UpperBound2(x) << "\n";
		if(q == 2) g << LowerBound(x) << "\n";
	}
}