时间限制：1秒　　内存限制：256M

---

【题目描述】

　　对于给定序列 \(A[1]..A[n]\)，请你设计一种数据结构实现 RMQ 问题：

　　1、Insert \(k\ v\)：在序列的第 \(k\) 个元素之后插入一个元素 \(v\)（如果 \(k==0\) 表示在第一个元素之前插入）。
　　2、Delete \(k\)：删除序列的第 \(k\) 个元素。
　　3、Add \(k\ v\)：把序列的第 \(k\) 个元素增加 \(v\)。
　　4、Max \(i\ j\)：查询区间：\(A[i],A[i+1]…,A[j]\) 范围内的最大元素的值。
　　5、Min \(i\ j\)：查询区间：\(A[i],A[i+1]…,A[j]\) 范围内的最小元素的值。

　　最初序列中有 \(n\) 个元素，依次为：\(A[1],A[2],..A[n]\)。

【输入格式】

　　第 1 行包含两个整数 \(n,m\)，其中 \(n\) 表示最初序列的元素个数，\(m\) 表示对序列维护和查询操作数目。
　　第 2 行包含 \(n\) 个整数，表示序列 \(A\) 中的元素 \(A[1]..A[n]（|A[i]|<=10^9）\)。
　　接下来的 \(m\) 行，每行的第一项是操作单词，分别是 Insert，Delete，Add,Max,Min 等操作，所有操作均合法，其中\(（0≤|v|≤10^9）\)。

【输出格式】

　　输出 Max 和 Min 查询的结果。

【输入输出样例】

　Input

10 15
3 2 9 2 1 10 6 5 8 7
Max 2 8
Min 3 10
Insert 7 0
Insert 0 20
Delete 6
Add 2 10
Max 2 9
Min 1 10
Max 1 6
Insert 8 -4
Delete 1
Delete 10
Insert 10 16
Min 5 11
Max 7 11

　Output

10
1
13
0
20
-4
16

【数据限制】

　　对于 \(100\%\) 的数据，\(n,m≤200000\)

【来源】

　　Mr.he**