#include<bits/stdc++.h>
using namespace std;
const int N=100020;
int n, a[N],m;
int caut0(int x){
	int dr=n, st=1, m=(1+n)/2;
	while(st<=dr){
		m=(st+dr)/2;
		if(a[m]<=x)st=m+1; else dr=m-1;
	}
	m=(st+dr)/2;
	if(a[m]>x)m--;
	if(a[m]==x)return m; else return -1;
}
int caut1(int x){
	int dr=n, st=1, m;
	while(st<=dr){
		m=(st+dr)/2;
		if(a[m]<=x)st=m+1; else dr=m-1;
	}
	m=(st+dr)/2;
	if(a[m]>x)m--;
	return m;
}
int caut2(int x){
	int st=1, dr=n, m;
	while(st<=dr){
		m=(st+dr)/2;
		if(a[m]>=x)dr=m-1; else st=m+1;
	}
	m=(st+dr)/2;
	if(a[m]<x)m++;
	return m;
}
int main(){
	ifstream f("cautbin.in");
	ofstream g("cautbin.out");
	f>>n;
	for(int i=1;i<=n;i++)f>>a[i];
	f>>m;
	while(m--){
		int k, v;
		f>>k>>v;
		if(k==0){
			g<<caut0(v)<<'\n';
			continue;
		}
		if(k==1){
			g<<caut1(v)<<'\n';
			continue;
		}
		g<<caut2(v)<<'\n';
	}
	
}