#include<bits/stdc++.h>
using namespace std;
const int N=1000005,INF=0x3f3f3f3f;
int a[N];
struct node{
	node *left,*right,*dad;
	int mx,l,r;
}pool[N<<2],*root=nullptr,*ma[N];
int cnt;
node* New(node* fa,int x,int l,int r){
	pool[cnt]=node{nullptr,nullptr,fa,x,l,r};
	return pool+(cnt++);
}
void sol(node* p){p->mx=max(p->left->mx,p->right->mx);}
node* build(int l,int r,node* fa){
	if(l+1==r) return (ma[l]=New(fa,a[l],l,r));
	int mid=l+(r-l)/2;
	node* p=New(fa,0,l,r);
	p->left=build(l,mid,p);
	p->right=build(mid,r,p);
	sol(p);
	return p;
}
void update(node* p,int l,int r,int pos,int x){
	if(l+1==r){
		p->mx=x;
		return;
	}
	int mid=l+(r-l)/2;
	if(pos<mid) update(p->left,l,mid,pos,x);
	else update(p->right,mid,r,pos,x);
	sol(p);
}
int query(node* p,int L,int R,int l,int r){
	if(l>=r) return -INF;
	if(l<=L && R<=r) return p->mx;
	int mid=L+(R-L)/2,ans=-INF;
	if(l<mid) ans=max(ans,query(p->left,L,mid,l,r));
	if(r>mid) ans=max(ans,query(p->right,mid,R,l,r));
	return ans;
}
int searchpre(node* p,int l,int r,int x){
	if(l+1==r) return l;
	int mid=l+(r-l)/2;
	if(p->right->mx>x) return searchpre(p->right,mid,r,x);
	return searchpre(p->left,l,mid,x);
}
int findpre(int pos,int x){
	node* p=ma[pos];
	while(p!=root){
		if(p==p->dad->right){
			node* r=p->dad->left;
			if(r->mx>x) return searchpre(r,r->l,r->r,x);
		}
		p=p->dad;
	}
	return -1;
}
int searchnxt(node* p,int l,int r,int x){
	if(l+1==r) return l;
	int mid=l+(r-l)/2;
	if(p->left->mx>x) return searchnxt(p->left,l,mid,x);
	return searchnxt(p->right,mid,r,x);
}
int findnxt(int pos,int x){
	node* p=ma[pos];
	while(p!=root){
		if(p==p->dad->left){
			node* r=p->dad->right;
			if(r->mx>x) return searchnxt(r,r->l,r->r,x);
		}
		p=p->dad;
	}
	return -1;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int n,q;
	cin >> n >> q;
	for(int i=0;i<n;++i) cin >> a[i];
	root=build(0,n,nullptr);
	while(q--){
		char op;
		cin >> op;
		if(op=='U'){
			int pos,val;
			cin >> pos >> val;
			--pos;
			a[pos]=val;
			update(root,0,n,pos,val);
		}else{
			int x;
			char d=op;
			cin >> x;
			--x;
			if(d=='L'){
				const int lmx=query(root,0,n,0,x),rmx=query(root,0,n,x+1,n);
				if(lmx<a[x]) cout << x+1 << '\n';
				else if(lmx>rmx) cout << findpre(x,max(a[x],rmx))+1 << '\n';
				else cout << findnxt(x,lmx)+1 << '\n';	
			}else{
				const int lmx=query(root,0,n,0,x),rmx=query(root,0,n,x+1,n);
				if(rmx<a[x]) cout << x+1 << '\n';
				else if(lmx<rmx) cout << findnxt(x,max(a[x],lmx))+1 << '\n';
				else cout << findpre(x,rmx)+1 << '\n';	
			}
		}
	}
	return 0;
}