玻利维亚是一个文化和历史悠久的南美国家，拥有丰富的自然奇观，包括部分亚马逊雨林和安第斯山脉。更重要的是，对于我们的参赛选手来说，它将是下一届国际信息学奥林匹克竞赛（IOI）的举办地！

为了宣传这次比赛，组织者受命拍摄山脉并制作一本最令人叹为观止的相册。山脉被表示为一个包含 $N$ 个非负整数的数组 $v$，其中 $v_i$ 表示第 $i$ 座山的高度。保证 $N$ 为奇数，且位于位置 $\frac{N+1}{2}$ 的最高山峰是死火山内瓦多萨哈马（Nevado Sajama）。

组织者对照片有非常具体的要求。首先，他们选择两个非负整数 $A$ 和 $B$，使得 $A < B$ 且 $B$ 小于或等于内瓦多萨哈马的高度。然后，他们调整相机，使照片的宽度能够捕捉到所有 $N$ 座山，但垂直范围仅限于 $A$ 和 $B$ 之间。此外，只有当照片关于穿过中心山峰的垂直轴对称时，组织者才会满意。

插图：对应第二个样例的有效照片选择示例

组织者现在想知道他们可以拍摄多少种不同的照片——也就是说，有多少对 $(A, B)$ 满足给定的条件。在思考答案的过程中，强烈的构造运动导致一些山峰的高度发生了变化。总共发生了 $Q$ 次高度变化，你的任务是帮助组织者确定每次变化后有效照片的数量。重要的是，没有任何变化会影响中心山峰的高度，它始终保持为最高山峰。

输入格式

第一行包含两个正整数 $N$ 和 $Q$，分别表示山峰的数量和高度变化的次数。

第二行包含一个包含 $N$ 个非负整数的数组 $v$，按顺序表示山峰的高度。保证 $N$ 为奇数，且中心山峰最高。

接下来的 $Q$ 行，每行包含两个非负整数 $x_i$ 和 $h_i$ ($1 \le x_i \le N$)，表示位置 $x_i$ 处的山峰高度变为 $h_i$。保证 $x_i \neq \frac{N+1}{2}$，且新高度小于或等于中心山峰的高度。

输出格式

输出 $Q+1$ 行。第 $i$ 行输出前 $i-1$ 次高度变化后有效照片的数量。

数据范围

在所有子任务中，满足 $3 \le N \le 200\,000$ 且 $0 \le Q \le 200\,000$。

对于所有 $i = 1, \dots, N$，满足 $v_i \le 654\,200$（内瓦多萨哈马的高度，单位为厘米）。

样例

输入 1

5 5
1 5 8 7 3
1 8
4 1
2 0
4 0
5 8

输出 1

5
6
1
3
6
36

输入 2

7 0
4 3 1 7 2 3 5

输出 2

7

输入 3

7 10
1 6 7 10 5 4 3
2 7
2 8
2 9
2 9
2 10
6 5
6 6
6 7
6 8
6 9

输出 3

8
8
5
3
3
2
4
4
4
5
7

说明

第二个样例的解释： 有效的 $(A, B)$ 选择为：$(0, 1), (2, 3), (2, 4), (3, 4), (5, 6), (5, 7), (6, 7)$。总共有七对。 上图对应于 $A = 2$ 且 $B = 4$ 的选择。