Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
K. Maximum Rating
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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.

Example
Input
3 5
1 2 3
3 4
2 -2
1 -3
3 1
2 1
Output
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.