Maximum Rating

题目描述

A rating system, usually used in sports, games, and competitive programming platforms, is a method to rank the skill level of their players or users in relatively impartial ways. The rating of an individual is the numerical evaluation of competitive performance, which is directly comparable even at different times.

Sulfox is an ICPC contestant who has participated in $n$ AtForces rounds, where the rating change for the $i$-th round is $a_i$. The initial rating and maximum rating are both $0$. After each round, the rating is increased by the rating change for that round. If the rating at that point is strictly greater than the current maximum rating, the maximum rating will be updated to the current rating.

Now Sulfox has hacked into AtForces' back-end database, which enables him to arrange these $n$ rounds in any order. He wonders how many values of $k$ exist satisfying that there is at least an arrangement of the $n$ rounds that updates the maximum rating exactly $k$ times. Additionally, he wants to know the result each time after some updates that modify the rating change for one of the $n$ rounds.

翻译

评级系统通常用于体育、游戏和竞技编程平台，是一种以相对公正的方式对玩家或用户的技能水平进行排名的方法。对个人的评级是对竞技表现的数字评估，即使在不同时间也可直接比较。

Sulfox 是一名参加过 $n$ 的 ICPC 选手。AtForces Round，其中 $i$ /-th回合的评分变化为 $a_i$ 。初始等级和最高等级都是 $0$ 。每一轮结束后，等级会根据该轮的等级变化而增加。如果此时的等级严格大于当前的最高等级，则最高等级将更新为当前等级。

现在，Sulfox 侵入了 AtForces 的后端数据库，这使他能够以任意顺序排列这些 $n$ 回合。他想知道有多少个 $k$ 的值可以满足至少有一种 $n$ 回合的排列组合可以精确地更新最大评分 $k$ 次。此外，他还想知道每次更新后的结果，这些更新修改了 $n$ 轮中某一轮的评分变化。

输入格式

The first line contains two integers $n$ and $q$ ($1 \le n,q \le 2\times 10^5$), denoting the number of AtForces rounds and the number of updates respectively.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), denoting the rating changes for each round.

Then $q$ lines follow, each containing two integers $x$ ($1 \le x \le n$) and $v$ ($-10^9 \le v \le 10^9$), denoting an update that modifies the rating change for the $x$-th round to $v$.

输出格式

After each update, output a line containing an integer, representing the number of $k$ satisfying that there exists at least an arrangement of the $n$ rounds where the maximum rating is updated exactly $k$ times.

样例 #1

样例输入 #1

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

样例输出 #1

1
2
2
2
3

提示

Note

In the sample case:

• After the first update, the rating changes for each round are $[1,2,4]$, and the maximum rating can only be updated $3$ times.
• After the second update, the rating changes for each round are $[1,-2,4]$, and the maximum rating can be updated $1$ or $2$ times.
• After the third update, the rating changes for each round are $[-3,-2,4]$, and the maximum rating can be updated $0$ or $1$ times.
• After the fourth update, the rating changes for each round are $[-3,-2,1]$, and the maximum rating can be updated $0$ or $1$ times.
• After the fifth update, the rating changes for each round are $[-3,1,1]$, and the maximum rating can be updated $0$, $1$, or $2$ times.