E: 総和の切り取り

問題

えびちゃんは数列 (a_1, a_2, ..., a_n) を持っています。 えびちゃんは（空でもよい）部分配列の総和の最大値が気になるので、それを求めてください。 ここで、部分配列とは連続する部分列を指します。なお、空列の総和は 0 とします。

さらに、えびちゃんがこの数列を q 回書き換えるので、各書き換えの直後にこの値を求めてください。

入力形式

n q
a_1 a_2 ... a_n
k_1 x_1
...
k_q x_q

各 k_j, x_j (1 \leq j \leq q) は、a_{k_j} を x_j に書き換えることを意味します。 各書き換えは独立ではなく、その後の処理において配列は書き換えられたままであることに注意してください。

制約

• 1\leq n\leq 10^5
• 1\leq q\leq 10^5
• 1\leq k_j\leq n
• |a_i|, |x_j| \leq 10^9

出力形式

q+1 行出力してください。1 行目には書き換えを行う前の、1+i 行目には i 回目の書き換えの直後の部分配列の総和の最大値を出力してください。

入力例1

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

出力例1

4
10
7

部分配列 (a_l, …, a_r) を a[l, r] と表すことにすると、書き換え前は a[1, 4] および a[4, 4] の総和が 4 で、これが最大です。

1 回目の書き換えの後、数列は (1, 2, 3, 4, -5) となり、総和の最大値は a[1, 4] の 10 です。

2 回目の書き換えの後、数列は (1, -6, 3, 4, -5) となり、総和の最大値は a[3, 4] の 7 です。

入力例2

3 1
-1 -2 -3
1 1

出力例2

0
1

空列の総和は 0 であり、書き換え前はそれが最大です。

---