#include <fstream>
using namespace std;

ifstream f ("cautbin.in");
ofstream g ("cautbin.out");

int main ()
	{
	int n,m,v[100001],i,q,e,a,b,x;
	
	f>>n;
	for (i=1; i<=n; i++)
		f>>v[i];
	f>>m;

	for (i=0; i<m; i++)
		{
		f>>q>>e;
		a=0; b=n-1;

		if (q==0)
			{
			while (a<=b)			
				{
				x=a+(b-a)/2;
				if (v[x]==e)
					a=b+1;
				if (v[x]>e)
					b=x-1;
				if (v[x]<e)
					a=x+1;
				}
			if (v[x]!=e)
				g<<-1;
			else
				{
				while (v[x]==v[x+1])
					x+=1;
				g<<x<<'\n';
				}
			}
		
		if (q==1)
			{
			while (a<=b)
				{
				x=a+(b-a)/2;
				if (v[x]<=e && v[x+1]>v[x])
					a=b+1;
				else
					{
					if (v[x]>e)
						b=x-1;	
					if (v[x]<=e)
						a=x+1;
					}
				}
			g<<x<<'\n';
			}

		if (q==2)
			{
			while (a<=b)
				{
				x=a+(b-a)/2;
				if (v[x]>=e && v[x]>v[x-1])
					a=b+1;
				else
					{
					if (v[x]>=e)
						b=x-1;
					if (v[x]<e)
						a=x+1;
					}
				}
			g<<x<<'\n';
			}
		}

	g.close();
	return 0;
	}