#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;}
		g<<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;
}