Descrizione
Helloooo! Can you hear me?
Ti viene data una sequenza $A = (A_1, A_2, \dots, A_N)$ di lunghezza $N$ composta da interi maggiori o uguali a $-1$. Utilizzando questa sequenza e un parametro $c$, esegui le seguenti operazioni:
- Inizialmente, imposta la variabile $x := 0$.
- Per $i = 1, 2, \dots, N$, ripeti la seguente operazione:
- Se $A_i = -1$, aggiorna $x$ a $x := \max(0, x - c)$.
- Altrimenti, aggiorna $x$ a $x := x + A_i$.
Rispondi a $Q$ domande della seguente forma:
- Quando il parametro è $c = C_i$, trova il valore massimo raggiunto da $x$ durante l'intera sequenza di operazioni.
Input
La prima riga contiene due interi $N$ e $Q$ ($1 \le N, Q \le 3 \times 10^5$). La seconda riga contiene $N$ interi $A_i$ ($-1 \le A_i \le 10^6$). Ciascuna delle successive $Q$ righe contiene un intero $C_i$, che rappresenta il valore del parametro per la $i$-esima domanda ($0 \le C_i \le 10^6$).
Output
Stampa $Q$ righe. Sulla $i$-esima riga, stampa la risposta alla $i$-esima domanda.
Esempi
Input 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
Output 1
1700 1550 1400 950 570 500 500 850 500 500 1850
Note
Spieghiamo la prima domanda del primo esempio di input:
- In questa domanda, il parametro è $c = 30$.
- Inizialmente, $x = 0$.
- Poiché $A_1 = 50$, $x$ viene aggiornato a $x = 0 + 50 = 50$.
- Poiché $A_2 = 100$, $x$ viene aggiornato a $x = 50 + 100 = 150$.
- ...
- Poiché $A_6 = 200$, $x$ viene aggiornato a $x = 300 + 200 = 500$.
- Poiché $A_7 = -1$, $x$ viene aggiornato a $x = \max(0, 500 - 30) = 470$.
- ...
- Poiché $A_{19} = -1$, $x$ viene aggiornato a $x = \max(0, 1530 - 30) = 1500$.
- Poiché $A_{20} = 200$, $x$ viene aggiornato a $x = 1500 + 200 = 1700$.
Includendo le parti omesse, il valore massimo raggiunto da $x$ durante l'intera sequenza di operazioni è $1700$.