#include<fstream>

using namespace std;

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

int n,a[100005],m,i,q,nr;
 
int cautbin1(int val)
{
    int i,pas;
    for(pas=1;pas<=n;pas<<=1);
    for(i=0;pas;pas>>=1)
        if(i+pas<=n && a[i+pas]==val)
           i+=pas;
    if(!i)return -1;
    else return i;
}

int cautbin2(int val)
{
	int i,pas;
	for(pas=1;pas<=n;pas<<=1);
    for(i=0;pas;pas>>=1)
        if(i+pas<=n && a[i+pas]<=val)
           i+=pas;
    return i;
}

int cautbin3(int val)
{
	int i,pas;
	for(pas=1;pas<n;pas<<=1);
    for(i=n;pas;pas>>=1,--i)
        if(i+pas<n && a[i+pas]>=val)
           i+=pas;
	return i;
}

main(void)
{
	cin>>n;
	for(i=1;i<=n;++i)cin>>a[i];
	cin>>m;
	for(i=1;i<=m;++i){
		cin>>q>>nr;
		if(!q)cout<<cautbin1(nr)<<'\n';
		else if(q==1)cout<<cautbin2(nr)<<'\n';
		else if(q==2)cout<<cautbin3(nr)<<'\n';
	}
}