#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int i,x,j,k,v[100001],tip,n,z;
int caut(int x,int y,int r)
{
	int k=-1,w=0;
	while(y-x>1)
	{
		w=(x+y)/2;
		if(v[w]<=r)
		{
			if(v[w]==r)
				k=w;
			x=w;
		}
		else
		{
			y=w;
		}
	}
	return k;
}
int caut2(int x,int y,int r)
{
	int k=-1,w=0;
	while(y-x>1)
	{
		w=(x+y)/2;
		if(v[w]<=r)
		{
			k=w;
			x=w;
		}
		else
		{
			y=w;
		}
	}
	return k;
}
int caut3(int x,int y,int r)
{
	int k=-1,w=0;
	while(y-x>1)
	{
		w=(x+y)/2;
		if(v[w]>=r)
		{
			k=w;			
			y=w;
		}
		else
		{
			x=w;
		}
	}
	return k;
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i];
    }
    fin>>k;
    for(i=1;i<=k;i++)
    {
        fin>>tip>>x;
        tip++;
        if(tip==1)
		{
			z=caut(1,n,x);
            fout<<z<<"\n";
		}
        else
            if(tip==2)
            {   
				z=caut2(1,n,x);
				fout<<z<<"\n";
            }
            else
			{
				z=caut3(1,n,x);
                fout<<z<<"\n";
			}
    }
    return 0;
}