題目描述
Helloooo! Can you hear me?
俾定一個長度為 $N$ 嘅序列 $A = (A_1, A_2, \dots, A_N)$,其中每個元素都大於或等於 $-1$。用呢個序列同埋一個參數 $c$,執行以下操作:
- 初始時,設變數 $x := 0$。
- 對於 $i = 1, 2, \dots, N$,重複執行以下操作:
- 如果 $A_i = -1$,就將 $x$ 更新為 $x := \max(0, x - c)$。
- 否則,將 $x$ 更新為 $x := x + A_i$。
回答 $Q$ 個以下形式嘅問題:
- 當參數 $c = C_i$ 嗰陣,求喺成個操作序列入面 $x$ 可以達到嘅最大值。
輸入格式
第一行包含兩個整數 $N$ 同 $Q$($1 \le N, Q \le 3 \times 10^5$)。 第二行包含 $N$ 個整數 $A_i$($-1 \le A_i \le 10^6$)。 接住落嚟嘅 $Q$ 行,每行包含一個整數 $C_i$,代表第 $i$ 個問題嘅參數值($0 \le C_i \le 10^6$)。
輸出格式
輸出 $Q$ 行。 喺第 $i$ 行輸出第 $i$ 個問題嘅答案。
範例
範例輸入 1
20 11 50 100 50 100 0 200 -1 50 100 -1 200 -1 200 0 200 -1 200 200 -1 200 30 60 90 180 270 360 540 200 400 600 0
範例輸出 1
1700 1550 1400 950 570 500 500 850 500 500 1850
備註
下面解釋第一個範例輸入入面嘅第一個問題:
- 喺呢個問題入面,參數 $c = 30$。
- 初始時,$x = 0$。
- 因為 $A_1 = 50$,$x$ 更新為 $x = 0 + 50 = 50$。
- 因為 $A_2 = 100$,$x$ 更新為 $x = 50 + 100 = 150$。
- ...
- 因為 $A_6 = 200$,$x$ 更新為 $x = 300 + 200 = 500$。
- 因為 $A_7 = -1$,$x$ 更新為 $x = \max(0, 500 - 30) = 470$。
- ...
- 因為 $A_{19} = -1$,$x$ 更新為 $x = \max(0, 1530 - 30) = 1500$。
- 因為 $A_{20} = 200$,$x$ 更新為 $x = 1500 + 200 = 1700$。
計埋省略咗嘅部分,喺成個操作序列入面 $x$ 可以達到嘅最大值係 $1700$。