该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 $n$ 的序列，有 $m$ 次修改

每次修改将某个位置上的数字 $+1$ 或 $-1$

每次修改完输出 $\sum_{l=1}^n\sum_{r=l}^n(max_{k=l}^r a_k-min_{k=l}^ra_k)$

输入格式

第一行两个整数 $n,m$

第二行 $n$ 个整数 $a_1\sim a_n$

接下来 $m$ 行，每行一个字符 $c$ 和一个整数 $x$。

如果 $c$ 是 $+$ 则令 $a[x]+1$

如果 $c$ 是 $-$ 则令 $a[x]-1$

输出格式

每次修改完输出答案

Samples

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

0
2
5
8
5
6

Limitation

对于 $？\%$ 的数据：数据随机生成

对于 $100\%$ 的数据：$1\leq n,m\leq 5*10^5$，$1\leq |a_i|\leq 10^9$,$1\leq x\leq n$，$c\in ['+','-']$ 。