using namespace std;
const int N = 2000010;
const int INF = 1 << 30;

struct Treap {
  int rt, cnt[N], dat[N], son[N][2], val[N], siz[N];
  void split(int p, int x, int &l, int &r) {
    if (!p) { l = r = 0; return; }
    if (val[p] <= x) {
        l = p;
        split(son[p][1], x, son[p][1], r);
    } else {
        r = p;
        split(son[p][0], x, l, son[p][0]);
    }
    siz[p] = siz[son[p][0]] + siz[son[p][1]] + 1;
}

int merge(int l, int r) {
    if (!l || !r) return l + r;
    if (dat[l] > dat[r]) {
        son[l][1] = merge(son[l][1], r);
        siz[l] = siz[son[l][0]] + siz[son[l][1]] + 1;
        return l;
    } else {
        son[r][0] = merge(l, son[r][0]);
        siz[r] = siz[son[r][0]] + siz[son[r][1]] + 1;
        return r;
    }
}

void insert(int x) {
    static int idx = 0;
    int l, r;
    split(rt, x, l, r);
    val[++idx] = x;
    dat[idx] = rand();
    siz[idx] = 1;
    rt = merge(merge(l, idx), r);
}

void remove(int x) {
    int l, r, p;
    split(rt, x, l, r);
    split(l, x-1, l, p);
    if (p) {
        p = merge(son[p][0], son[p][1]);
        rt = merge(merge(l, p), r);
    } else {
        rt = merge(l, r);
    }
}

int rnk(int x) {
    int l, r;
    split(rt, x-1, l, r);
    int res = siz[l] + 1;
    rt = merge(l, r);
    return res;
}

int kth(int p, int k) {
    if (k == siz[son[p][0]] + 1) return p;
    if (k <= siz[son[p][0]]) return kth(son[p][0], k);
    return kth(son[p][1], k - siz[son[p][0]] - 1);
}

int get_pre(int x) {
    int l, r;
    split(rt, x-1, l, r);
    int res = -INF;
    if (l) res = val[kth(l, siz[l])];
    rt = merge(l, r);
    return res;
}

int get_nxt(int x) {
    int l, r;
    split(rt, x, l, r);
    int res = INF;
    if (r) res = val[kth(r, 1)];
    rt = merge(l, r);
    return res;
}

} sgap, mgap;

int last[N];            // 新增：记录每个位置最后一个元素
int min_sort_gap = INF; // 新增：维护全局最小排序差
int s[N],sm[N];
int main() {
  int n, m;
  cin >> n >> m;

  // 初始化部分
  for (int i = 1; i <= n; i++) {
    int a;
    cin >> s[i];
    last[i] = s[i];sm[i]=s[i ];// 记录最后元素
    sgap.insert(s[i]);
    if (i > 1) {
      mgap.insert(abs(s[i] - s[i - 1]));
    }
  }

  // 初始化最小排序差
  sort(sm+1,sm+1+n);
  for(int i=1;i<n;i++){
  	min_sort_gap=min(min_sort_gap,sm[i+1]-sm[i]);
  }

  while (m--) {
    string opt;
    cin >> opt;
    if (opt == "INSERT") {
      int pos, k;
      cin >> pos >> k;

      mgap.remove(abs(last[pos] - s[pos + 1])); // 删除旧差
      mgap.insert(abs(k - s[pos + 1]));         // 插入新差
      mgap.insert(abs(k - last[pos]));          // 插入前差

      int pre = sgap.get_pre(k);
      int nxt = sgap.get_nxt(k);
      min_sort_gap = min(min_sort_gap, k - pre);
      min_sort_gap = min(min_sort_gap, nxt - k);
      sgap.insert(k);

      last[pos] = k;
    } else if (opt == "MIN_GAP") {
      cout << mgap.kth(mgap.rt, 1) << endl;
    } else if (opt == "MIN_SORT_GAP") {
      cout << min_sort_gap << endl;
    }
  }
  return 0;
}