给定一个包含 $n$ 个整数的序列 $a_1, \dots, a_n$。该序列将进行总共 $q$ 次操作。每次操作涉及将序列中的单个元素增加或减少 1。在每次操作后，请输出以下表达式的值：

$$\sum_{i=1}^{n} \sum_{j=i}^{n} \left( \max_{i \le k \le j} (a_k) - \min_{i \le k \le j} (a_k) \right)$$

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 500\,000$)，分别表示序列的长度和操作次数。第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($|a_i| \le 100\,000$)，表示序列元素的初始值。接下来的 $q$ 行描述了各项操作。每项操作属于以下两种类型之一：

• 符号 + 和一个整数 $p$ ($1 \le p \le n$) —— 将 $a_p$ 的值增加 1 的操作。
• 符号 - 和一个整数 $p$ ($1 \le p \le n$) —— 将 $a_p$ 的值减少 1 的操作。

输出格式

输出应包含 $q$ 行，每行包含一个整数。第 $i$ 行的数字应为执行前 $i$ 次操作后该表达式的值。

样例

样例输入 1

3 6
0 0 -1
+ 3
+ 3
- 2
- 2
+ 2
+ 1

样例输出 1

0
2
5
8
5
6

说明

连续操作后的序列如下所示：

• $0, 0, 0$
• $0, 0, 1$
• $0, -1, 1$
• $0, -2, 1$
• $0, -1, 1$
• $1, -1, 1$