评分系统通常用于体育、游戏和程序设计竞赛平台，是一种以相对公正的方式对选手或用户的技能水平进行排名的方法。个人的评分是对竞技表现的数值评估，即使在不同时间点也具有直接的可比性。

Sulfox 是一名 ICPC 选手，他参加了 $n$ 场 AtForces 比赛，其中第 $i$ 场比赛的评分变化为 $a_i$。初始评分和最高评分均为 $0$。每场比赛结束后，评分会增加该场比赛的评分变化值。如果此时的评分严格大于当前的最高评分，则最高评分将更新为当前的评分。

现在，Sulfox 入侵了 AtForces 的后端数据库，这使他能够以任意顺序安排这 $n$ 场比赛。他想知道有多少个 $k$ 值满足：存在至少一种 $n$ 场比赛的排列方式，使得最高评分恰好更新 $k$ 次。此外，他想知道在进行一些修改其中一场比赛评分变化的更新操作后，每次更新后的结果。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 2 \times 10^5$)，分别表示 AtForces 比赛的场数和更新次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，表示每场比赛的评分变化。

接下来 $q$ 行，每行包含两个整数 $x$ ($1 \le x \le n$) 和 $v$ ($-10^9 \le v \le 10^9$)，表示将第 $x$ 场比赛的评分变化修改为 $v$ 的更新操作。

输出格式

在每次更新后，输出一行包含一个整数，表示满足“存在至少一种 $n$ 场比赛的排列方式，使得最高评分恰好更新 $k$ 次”的 $k$ 的个数。

样例

输入 1

3 5
1 2 3
3 4
2 -2
1 -3
3 1
2 1

输出 1

1
2
2
2
3

说明

在样例中：

• 第一次更新后，各场比赛的评分变化为 $[1, 2, 4]$，最高评分只能更新 $3$ 次。
• 第二次更新后，各场比赛的评分变化为 $[1, -2, 4]$，最高评分可以更新 $1$ 次或 $2$ 次。
• 第三次更新后，各场比赛的评分变化为 $[-3, -2, 4]$，最高评分可以更新 $0$ 次或 $1$ 次。
• 第四次更新后，各场比赛的评分变化为 $[-3, -2, 1]$，最高评分可以更新 $0$ 次或 $1$ 次。
• 第五次更新后，各场比赛的评分变化为 $[-3, 1, 1]$，最高评分可以更新 $0$ 次、$1$ 次或 $2$ 次。