#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int main()
{
	int m,n,i,mij,v[100001],p1=-1,p2=-1,p3,a,b,q,r;
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>v[i];
	fin>>m;
	for(i=1;i<=m;i++)
	{
		fin>>q>>r;
		p1=-1;
		p2=-1;
		p3=n+1;
		if(q%3==0)
		{
		    a=1;
			b=n;
			mij=(a+b)/2;
			while(a<=b)
			{
			    if(v[mij]==r)
			    {
				    if(mij>p1)p1=mij;
				    a=mij+1;
			    }
			    else
		    	{
			    	if(v[mij]<r)a=mij+1;
					else b=mij-1;
			    }
			    mij=(a+b)/2;
			}
			fout<<p1<<'\n';
		}
		else
		{
			if(q%3==1)
			{
				a=1;
			    b=n;
			    mij=(a+b)/2;
			    while(a<=b)
			    {
					if(v[mij]<=r)
			        {
				        if(mij>p2)p2=mij;
				        a=mij+1;
				    }						
					else
		         	{
			    	    if(v[mij]<r)a=mij+1;
					    else b=mij-1;
			        }
			        mij=(a+b)/2;
				}
				fout<<p2<<'\n';
			}
			else
			{
				a=1;
			    b=n;
			    mij=(a+b)/2;
			    while(a<=b)
			    {
					if(v[mij]>=r)
			        {
				        if(mij<p3)p3=mij;
				        b=mij-1;
			        }
			        else a=mij+1;
			        mij=(a+b)/2;
				}
			    fout<<p3<<'\n';
			}
		}
	}
	fin.close();
	fout.close();
	return 0;
}