Beschreibung
Helloooo! Can you hear me?
Gegeben ist eine Folge $A = (A_1, A_2, \dots, A_N)$ der Länge $N$, die aus ganzen Zahlen größer oder gleich $-1$ besteht. Führen Sie mithilfe dieser Folge und eines Parameters $c$ die folgenden Operationen aus:
- Setzen Sie zu Beginn die Variable $x := 0$.
- Wiederholen Sie für $i = 1, 2, \dots, N$ die folgende Operation:
- Falls $A_i = -1$, aktualisieren Sie $x$ auf $x := \max(0, x - c)$.
- Andernfalls aktualisieren Sie $x$ auf $x := x + A_i$.
Beantworten Sie $Q$ Fragen der folgenden Form:
- Wenn der Parameter $c = C_i$ ist, bestimmen Sie den maximalen Wert, den $x$ während der gesamten Operationsfolge annimmt.
Eingabe
Die erste Zeile enthält zwei ganze Zahlen $N$ und $Q$ ($1 \le N, Q \le 3 \times 10^5$). Die zweite Zeile enthält $N$ ganze Zahlen $A_i$ ($-1 \le A_i \le 10^6$). Jede der folgenden $Q$ Zeilen enthält eine ganze Zahl $C_i$, die den Parameterwert für die $i$-te Frage angibt ($0 \le C_i \le 10^6$).
Ausgabe
Geben Sie $Q$ Zeilen aus. Geben Sie in der $i$-ten Zeile die Antwort auf die $i$-te Frage aus.
Beispiele
Eingabe 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
Ausgabe 1
1700 1550 1400 950 570 500 500 850 500 500 1850
Hinweis
Wir erläutern die erste Frage der ersten Beispieleingabe:
- In dieser Frage ist der Parameter $c = 30$.
- Zu Beginn ist $x = 0$.
- Da $A_1 = 50$ ist, wird $x$ auf $x = 0 + 50 = 50$ aktualisiert.
- Da $A_2 = 100$ ist, wird $x$ auf $x = 50 + 100 = 150$ aktualisiert.
- ...
- Da $A_6 = 200$ ist, wird $x$ auf $x = 300 + 200 = 500$ aktualisiert.
- Da $A_7 = -1$ ist, wird $x$ auf $x = \max(0, 500 - 30) = 470$ aktualisiert.
- ...
- Da $A_{19} = -1$ ist, wird $x$ auf $x = \max(0, 1530 - 30) = 1500$ aktualisiert.
- Da $A_{20} = 200$ ist, wird $x$ auf $x = 1500 + 200 = 1700$ aktualisiert.
Einschließlich der ausgelassenen Teile beträgt der maximale Wert, den $x$ während der gesamten Operationsfolge annimmt, $1700$.