#include <bits/stdc++.h>
using namespace std;
 
int n,m,a[100100],x,y;
 
int search(int x){
	int st=1, dr=n, mid;
	while (st<=dr){
		mid=st+(dr-st)/2;
		if (a[mid]<=x) st=mid+1;
		else dr=mid-1;
	}
	if (a[dr]==y) return dr;
	else return -1;
}
 
int search2(int x){
	int st=1, dr=n, mid;
	while (st<=dr){
		mid=st+(dr-st)/2;
		if (a[mid]<=x) st=mid+1;
		else dr=mid-1;
	}
	return dr;
}
 
int search3(int x){
	int st=1, dr=n, mid;
	while (st<=dr){
		mid=st+(dr-st)/2;
		if (a[mid]>=x) dr=mid-1;
		else st=mid+1;
	}
	return st;
}
 
int main(){
	ifstream cin ("cautbin.in");
	ofstream cout ("cautbin.out");
	cin>>n;
	for (int i=1; i<=n; i++) cin>>a[i];
	cin>>m;
	for (int i=1; i<=m; i++){
		cin>>x>>y;
		if (x==0) cout<<search(y)<<"\n";
		else if (x==1) cout<<search2(y)<<"\n";
		else cout<<search3(y)<<"\n";
	}
	return 0;
}