Сипаттамасы
Helloooo! Can you hear me?
Сізге $-1$-ден үлкен немесе оған тең бүтін сандардан тұратын ұзындығы $N$ болатын $A = (A_1, A_2, \dots, A_N)$ тізбегі берілген. Осы тізбекті және $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$ жолдың әрқайсысында $i$-ші сұрақтың параметр мәнін білдіретін бір бүтін $C_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$.