#include <iostream>
#include <set>

using namespace std;

const int kMaxN = 5e5 + 1;
  
int n, m, qwe = 1e9, lst[kMaxN], a[kMaxN];
multiset<int> d, s;


void S(int x) {
	multiset<int>::iterator it = s.lower_bound(x);
	if (it != s.end()) {
		qwe = min(qwe, abs(*it - x));
	}
	if (!s.empty() && it != s.begin()) {
		qwe = min(qwe, abs(x - *prev(it)));
	}
	s.insert(x);
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		lst[i] = a[i];
		S(a[i]);
		(i != 1) && (d.insert(abs(a[i] - a[i - 1])), 0);
	}
	for (int i = 1; i <= m; i++) {
		string op;
		cin >> op;
		if (op == "INSERT") {
			int j, k;
			cin >> j >> k;
			d.insert(abs(lst[j] - k)); 
			if (j < n) {
				d.insert(abs(k - a[j + 1]));
				d.erase(d.find(abs(lst[j] - a[j + 1])));
			}
			S(k);
			lst[j] = k;
		} else if (op == "MIN_GAP") {
			cout << (*s.begin()) << '\n';
		} else {
			cout << qwe << '\n';
		}
	}
	return 0;
}