Koniec kola: 20. január 2020 23:59
1 day
Počet bodov:
Popis:  12b
Program:  8b

Rok 2018 (rekonštruované podľa dobových záznamov):

“Tak, vítam Vás všetkých na Rade Trojstenu. Máme dnes celkom veľa vecí na práci. Takmer polovica pozícií v Trojstene je neobsadených… Hľadáme napríklad hlavného vedúceho KMS, vedúcich FKS, dievčatá do KSP,…”

“Muhahahahaa” pomyslel si Krtko. “Konečne sa zmocním všetkých pozícií v Trojstene. Teda, nie všetkých, ale len tých cool. Napríklad hlavný vedúci KMS naozaj nie je cool pozícia…”

“Takže, chce si niekto zobrať pozíciu dievčaťa v KSP?”

“Ja by som si to zobral”, ozval sa Krtko.

“Hlavného vedúceho KMS?”

“Nie, toto nechcem…”, povedal Krtko.

“Ale takto to nefunguje, Krtko… Ak si zoberieš nejakú pozíciu, tak si musíš zobrať všetky pozície od nej, až po poslednú.”

“No dobre, ako myslíte…”

Už dlhé roky sa v Trojstene traduje táto legenda, ale nikto doteraz nevie ako veľmi cool boli pozície, ktoré si Krtko zobral. Z dobových záznamov sa zachoval len počet pozícií, ktoré boli v ponuke, a cool-ovosť týchto pozícií. Vedeli by ste z týchto údajov vypočítať najväčšiu možnú coolovosť pozícií, ktoré si mohol Krtko zobrať?

Úloha:

Pre zadané coolovosti pozícií na vstupe, vypíšte maximálnu možnú coolovosť, ktoré je rovná súčtu coolovosti pozícií na neprázdnom intervale, ktorý končí na poslednom prvku poľa.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(n \leq 100000\) - počet pozícií, ktoré boli ponúknuté Krtkovi. Na druhom riadku sa nachádza \(n\) medzerou oddelených čísel, \(c_i\): \(-100000 \leq c_i \leq 100000\).

Formát výstupu

Vypíšte jedno číslo, maximálnu možnú coolovosť pozícií, ktore mohol Krtko získať.

Príklad

Input:

5
1 2 -5 10 2

Output:

12

Input:

3
10 -8 10

Output:

12

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.