Kuvaus
Helloooo! Can you hear me?
Sinulle annetaan pituutta $N$ oleva lukujono $A = (A_1, A_2, \dots, A_N)$, joka koostuu kokonaisluvuista, jotka ovat suurempia tai yhtä suuria kuin $-1$. Suorita tätä jonoa ja parametria $c$ käyttäen seuraavat operaatiot:
- Aseta aluksi muuttujan arvoksi $x := 0$.
- Toista arvoilla $i = 1, 2, \dots, N$ seuraava operaatio:
- Jos $A_i = -1$, päivitä $x$ arvoon $x := \max(0, x - c)$.
- Muussa tapauksessa päivitä $x$ arvoon $x := x + A_i$.
Vastaa $Q$ seuraavanlaiseen kysymykseen:
- Kun parametri on $c = C_i$, etsi suurin arvo, jonka $x$ saavuttaa koko operaatiojonon aikana.
Syöte
Ensimmäinen rivi sisältää kaksi kokonaislukua $N$ ja $Q$ ($1 \le N, Q \le 3 \times 10^5$). Toinen rivi sisältää $N$ kokonaislukua $A_i$ ($-1 \le A_i \le 10^6$). Kukin seuraavista $Q$ rivistä sisältää kokonaisluvun $C_i$, joka ilmaisee parametrin arvon $i$-nnessä kysymyksessä ($0 \le C_i \le 10^6$).
Tuloste
Tulosta $Q$ riviä. Tulosta $i$-nnelle riville vastaus $i$-nteen kysymykseen.
Esimerkit
Syöte 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
Tuloste 1
1700 1550 1400 950 570 500 500 850 500 500 1850
Huomautus
Selitämme ensimmäisen esimerkkisyötteen ensimmäisen kysymyksen:
- Tässä kysymyksessä parametri on $c = 30$.
- Aluksi $x = 0$.
- Koska $A_1 = 50$, $x$ päivittyy arvoon $x = 0 + 50 = 50$.
- Koska $A_2 = 100$, $x$ päivittyy arvoon $x = 50 + 100 = 150$.
- ...
- Koska $A_6 = 200$, $x$ päivittyy arvoon $x = 300 + 200 = 500$.
- Koska $A_7 = -1$, $x$ päivittyy arvoon $x = \max(0, 500 - 30) = 470$.
- ...
- Koska $A_{19} = -1$, $x$ päivittyy arvoon $x = \max(0, 1530 - 30) = 1500$.
- Koska $A_{20} = 200$, $x$ päivittyy arvoon $x = 1500 + 200 = 1700$.
Mukaan lukien pois jätetyt kohdat, suurin arvo, jonka $x$ saavuttaa koko operaatiojonon aikana, on $1700$.