#include<fstream>
#define max 100001
using namespace std;
ifstream f("cautbin.in");
ofstream g("cautbin.out");
int main(){
	int a,b,o,w,m,n,i,flg,h[max],x,y,z;
	f>>n>>m;
	for(i=1;i<=n;++i)
	f>>h[i];
	for(i=1;i<=m;++i)
	{
		f>>o>>w;
		x=-1; y=-1; z=1+n;
		if(o%3==0)
		{
			a=1;b=n;
			flg=(a+b)/2;
			while(a<b || a==b)
			{
				if(h[flg]==w)
				{
					if(flg>x)
					x=flg;
					a=flg+1;
				}
				else
				{
					if(h[flg]<w)a=flg+1;
					else b=flg-1;
				}
				flg=(a+b)/2;
			}
		f<<x<<endl;
		}
	else
	{
		if(o%3==1)
		{
			a=1;
			b=n;
			flg=(a+b)/2;
			while(a<b || a==b)
			{
				if(h[flg]<=w)
				{
					if(flg>y)y=flg;
					a=flg+1;
				}                       
				else
				{
					if(h[flg]<w)a=flg+1;
					else b=flg-1;
				}
				flg=(a+b)/2;
			}
			g<<y<<endl;
		}
		else
		{
			a=1; b=n;
			flg=(a+b)/2;
			while(a<=b)
			{
				if(h[flg]>=w)
				{
					if(flg<z)z=flg;
					b=flg-1;
				}
				else a=flg+1;
				flg=(a+b)/2;
			}
			g<<z<<endl;
		}
	}
	}
f.close();
g.close();
return 0;
}