[ZJOI2007]报表统计

小 Q 的妈妈是一名出纳，经常需要制作统计报表。今天是妈妈的生日，小 Q 希望帮妈妈分担一些工作，作为送给妈妈的生日礼物。

经过观察，小 Q 发现，统计一张报表实际上是在维护一个可能包含负数的整数数列，并进行以下三种操作：

• INSERT i k：在当前数列中第 $i$ 个元素后面添加一个新元素 $k$。如果该元素后面已经添加过若干元素，则将新元素添加在这些元素的最后面。
• MIN_GAP：查询当前数列中相邻两个元素的差值绝对值的最小值。
• MIN_SORT_GAP：查询当前数列中任意两个元素的差值绝对值的最小值。

例如，初始数列为 $5\ 3\ 1$。执行 INSERT 2 9 后，数列变为 $5\ 3\ 9\ 1$，此时 MIN_GAP 和 MIN_SORT_GAP 的答案均为 $2$。

继续执行 INSERT 2 6，数列变为 $5\ 3\ 9\ 6\ 1$。由于原数列的第 $2$ 个元素后面已经添加了元素 $9$，因此新元素 $6$ 应添加在 $9$ 的后面。此时 MIN_GAP 的答案为 $2$，MIN_SORT_GAP 的答案为 $1$。

请你帮助小 Q 改进程序，高效完成这些操作。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示初始数列的长度和操作次数。

第二行包含 $N$ 个整数，表示初始数列。

接下来的 $M$ 行每行包含一个操作，为以下三种操作之一：

• INSERT i k；
• MIN_GAP；
• MIN_SORT_GAP。

输入中没有多余的空格或空行。

输出格式

对于每个 MIN_GAP 和 MIN_SORT_GAP 操作，输出一行答案。

样例输入

3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

样例输出

2
2
1

样例解释

执行 INSERT 2 9 后，数列为 $5\ 3\ 9\ 1$，最小相邻差值和所有元素中的最小差值均为 $2$。

执行 INSERT 2 6 后，数列为 $5\ 3\ 9\ 6\ 1$，最小相邻差值为 $2$，所有元素中的最小差值为 $1$。

数据范围

• $N,M\le 5\times 10^5$；
• 对于所有数据，数列中的整数不超过 $5\times 10^8$。

来源与许可

本题为 ZJOI 2007 试题「报表统计」，题面与测试数据整理自 BZOJ 1058。

样例 1

输入

3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

输出

2
2
1