1e4的数据本地要十几秒，但复杂度应该就是大常数log

/*
    name: <[ZJOI2007] 报表统计>
    id:   <P1110>
    date: 2023/02/07
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 5e5 + 10;
int n, m, a[N], msga = 2147483647;
vector<int> p[N];
multiset<int> mg;
set<int> msg;
char ch[20];

void msgi(int x){
	auto i = lower_bound(msg.begin(), msg.end(), x);
	if(i == msg.end()){
		-- i;
		msga = min(msga, abs((*i) - x));
		msg.insert(x);
	} else if(i == msg.begin()){
		msga = min(msga, abs((*i) - x));
		msg.insert(x);
	} else {
		auto j = i;
		-- i;
		msga = min(msga, min(abs((*i) - x), abs((*j) - x)));
		msg.insert(x);
	}
}

void solve(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++ i){
		scanf("%d", &a[i]);
		if(i == 1){
			msg.insert(a[i]);
		} else {
			msgi(a[i]);
		}
		p[i].push_back(a[i]);
		if(i != 1){
			mg.insert(abs(a[i] - a[i-1]));
		}
	}
	while(m--){
		scanf("%s", ch);
		if(ch[4] == 'R'){
			int x, k;
			scanf("%d%d", &x, &k);
			msgi(k);
			int sz = p[x].size();
			if(x == n){
				mg.insert(abs(p[x][sz-1] - k));
				p[x].push_back(k);
			} else {
				auto i = lower_bound(mg.begin(), mg.end(), abs(p[x][sz-1] - a[x+1]));
				mg.erase(i);
				mg.insert(abs(p[x][sz-1] - k));
				mg.insert(abs(k - a[x+1]));
				p[x].push_back(k);
			}
		} else if(ch[4] == 'G'){
			printf("%d\n", *mg.begin());
		} else {
			printf("%d\n", msga);
		}
	}

}

int main(){
	solve();
	return 0;
}

//qwq