Server Time:

User's AC Ratio in this contest

25.0% (2/8)

Submission's AC Ratio in this contest

15.4% (2/13)

Description

自古以來男生在廁所方面有個刻在 DNA 上的默契,就是除非世界末日到了,不然絕對不會選旁邊有人的小便斗,而小嵐也不外乎。

因此小嵐根據這個默契發明了一個算法用來估計一間廁所的安全係數,首先小嵐會選定一間廁所,內含 $N$ 個小便斗,並且從 $1$ 編號到 $N$。

接著小嵐會為每個小便斗分配一個 $D$ 值作為那個小便斗的安全係數,而小嵐可以選擇隨意的便斗們將其安全係數相加起來就是廁所的安全係數,需要注意的是因為刻在 DNA 上的默契,因此挑選了一個便斗後它隔壁的便斗就不能再挑選了(例如挑選編號為 $3$ 的便斗後就不能再挑 $2$ 跟 $4$)。

但是因為小嵐很糊塗可能會給錯小便斗的安全係數,所以接下來小嵐會發出 $M$ 次修改,請在每次修改後告訴小嵐這間廁所可以獲得最高的安全係數。

Input Format

第一行有兩個整數 $N,M$,分別代表 $N$ 個小便斗和 $M$ 次修改。
第二行到第 $N+1$ 行有代表每個小便斗的初始 $D$ 值。
第 $N+2$ 到第 $N+M+1$ 行每行都有兩個整數 $X$ 和 $Y$ 代表將第 $X$ 個小便斗的值修改成 $Y$。

  • $1\leq N, M \leq 2\times 10^5$
  • $1\leq D, Y\leq 10^4$
  • $1\leq X\leq N$

Output Format

總共輸出 $M$ 行,對於每次的修改都輸出一次這間廁所可以獲的最高的安全係數。

Sample Input 1

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

Sample Output 1

14
15
21

Hints

原序列為 $8 3 2 1 5$
第一次修改後為 $8 3 2 1 4$,取第一、三、五加起來 14 為最大
第二次修改後為 $8 3 2 7 4$,取第一、四加起來 15 為最大
第三次修改後為 $8 3 9 1 4$,取第一、三、五加起來 21 為最大

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~55 無特別限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1
20 1000 65536 65536 1
21 1000 65536 65536 1
22 1000 65536 65536 1
23 1000 65536 65536 1
24 1000 65536 65536 1
25 1000 65536 65536 1
26 1000 65536 65536 1
27 1000 65536 65536 1
28 1000 65536 65536 1
29 1000 65536 65536 1
30 1000 65536 65536 1
31 1000 65536 65536 1
32 1000 65536 65536 1
33 1000 65536 65536 1
34 1000 65536 65536 1
35 1000 65536 65536 1
36 1000 65536 65536 1
37 1000 65536 65536 1
38 1000 65536 65536 1
39 1000 65536 65536 1
40 1000 65536 65536 1
41 1000 65536 65536 1
42 1000 65536 65536 1
43 1000 65536 65536 1
44 1000 65536 65536 1
45 1000 65536 65536 1
46 1000 65536 65536 1
47 1000 65536 65536 1
48 1000 65536 65536 1
49 1000 65536 65536 1
50 1000 65536 65536 1
51 1000 65536 65536 1
52 1000 65536 65536 1
53 1000 65536 65536 1
54 1000 65536 65536 1
55 1000 65536 65536 1