Beskrivelse
Helloooo! Can you hear me?
Du får gitt en følge $A = (A_1, A_2, \dots, A_N)$ med lengde $N$ som består av heltall større enn eller lik $-1$. Ved hjelp av denne følgen og en parameter $c$, utfør følgende operasjoner:
- Til å begynne med, sett variabelen $x := 0$.
- For $i = 1, 2, \dots, N$, gjenta følgende operasjon:
- Hvis $A_i = -1$, oppdater $x$ til $x := \max(0, x - c)$.
- Ellers, oppdater $x$ til $x := x + A_i$.
Svar på $Q$ spørsmål på følgende form:
- Når parameteren er $c = C_i$, finn den største verdien $x$ oppnår i løpet av hele operasjonsfølgen.
Inndata
Den første linjen inneholder to heltall $N$ og $Q$ ($1 \le N, Q \le 3 \times 10^5$). Den andre linjen inneholder $N$ heltall $A_i$ ($-1 \le A_i \le 10^6$). Hver av de følgende $Q$ linjene inneholder et heltall $C_i$, som representerer parameterverdien for det $i$-te spørsmålet ($0 \le C_i \le 10^6$).
Utdata
Skriv ut $Q$ linjer. På den $i$-te linjen skal du skrive ut svaret på det $i$-te spørsmålet.
Eksempler
Inndata 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
Utdata 1
1700 1550 1400 950 570 500 500 850 500 500 1850
Merk
Vi forklarer det første spørsmålet i det første eksempelets inndata:
- I dette spørsmålet er parameteren $c = 30$.
- Til å begynne med er $x = 0$.
- Siden $A_1 = 50$, oppdateres $x$ til $x = 0 + 50 = 50$.
- Siden $A_2 = 100$, oppdateres $x$ til $x = 50 + 100 = 150$.
- ...
- Siden $A_6 = 200$, oppdateres $x$ til $x = 300 + 200 = 500$.
- Siden $A_7 = -1$, oppdateres $x$ til $x = \max(0, 500 - 30) = 470$.
- ...
- Siden $A_{19} = -1$, oppdateres $x$ til $x = \max(0, 1530 - 30) = 1500$.
- Siden $A_{20} = 200$, oppdateres $x$ til $x = 1500 + 200 = 1700$.
Inkludert de utelatte delene er den største verdien $x$ oppnår i løpet av hele operasjonsfølgen $1700$.