#include <bits/stdc++.h>
using namespace std;
int n;
int num [1000005];
int a(int target,int l,int r)
{
	//求小于等于target的最后一个数的下标
	while(l<r)
	{
		int mid = l+r+1>>1;
		if(num[mid]<=target)l = mid;
		else r = mid - 1;
	}
	return l;	
}
int b(int target,int l,int r)
{
	//求大于等于target的第一个数的下标
	while(l<r)
	{
		int mid = l+r>>1;
		if(num[mid]>=target)r = mid;
		else l = mid + 1;	
	}
	return l;	
}
int c(int target,int l,int r)
{
	//小于target的最后一个数的下标
	while(l<r)
	{
		int mid = l+r+1>>1;
		if(num[mid]<target)l = mid;
		else r = mid - 1;
	}
	if(num[l]<target)return l;
	return -1;	
}
int d(int target,int l,int r)
{
	//´大于target的第一个数的下标
	while(l<r)
	{ 
		int mid = l+r>>1;
		if(num[mid]>target)r = mid;
		else l = mid + 1;
	}
	if(num[l]>target)return l;
	return -1;	
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;++i)cin>>num[i];
	while(m--)
	{
		int target;
		cin>>target;
		char x;
		cin>>x;
		cin.ignore();
		if(x=='A')cout<<a(target,0,n-1)<<endl;
		else if(x=='B')cout<<b(target,0,n-1)<<endl;
		else if(x=='C')cout<<c(target,0,n-1)<<endl;
		else cout<<d(target,0,n-1)<<endl;
	}
	return 0;
}