Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Šokinėjantis posekis

Seka b vadinama sekos a posekiu, jei seką b galima galima gauti iš sekos a pašalinant kažkiek elementų, nepakeičiant tvarkos. Pavyzdžiui, jei a=[1,2,3,3,4,6], tai šios sekos yra a posekiai: [1], [1,2,3,4,6], [3,3], [2,4,6], [3,6] ir t. t. Tačiau šios sekos posekiais nėra: [1,1], [1,7], [3,3,2] ir pnš.

Seką pavadinkime šokinėjančia, jei šios sekos visų gretimų elementų ženklai skiriasi. Tai yra, jei vienas sekos elementas yra teigiamas, tai jam gretimi sekos elementai turi būti neigiami. O jei vienas sekos elementas yra neigiamas, tai jam gretimi sekos elementai turi būti teigiami. Pavyzdžiui, sekos: [-1,10,-10,69], [69,-69,69,-69,69] ir [420,-69,69,-420] yra šokinėjančios, o sekos [-1,1,1,-6], [10,-3,-5,1] nėra šokinėjančios.

Jums duota seka a, sudaryta iš n elementų. Jums reikia surasti ilgiausią šokinėjantį a posekį. Tarp visų ilgiausių tokių posekių, jums reikia surasti tokį posekį, kurio elementų suma būtų didžiausia.

Kitaip tariant, jei ilgiausias šokinėjantis a sekos posekis yra ilgio k, tai jums reikia surasti, kokią didžiausią sumą gali turėti k ilgio šokinėjantis a sekos posekis.

Pradiniai duomenys

Pirmoje eilutėje pateiktas skaičius n (1\\leqn\\leq2*10^5). Antroje eilutėje pateikta n tarpais atskirtų skaičių a_1,a_2,...,a_n (-10^9\\leqa_i\\leq10^9,a_i\\neq0).

Rezultatai

Išveskite vieną skaičių - maksimalią ilgiausio šokinėjančio posekio sumą.

Pavyzdžiai

Duomenys Rezultatai Paaiškinimas 
4
4 1 2 -5
 
-1
 Ilgiausias įmanomas šokinėjantis posekis yra 2 elementų ilgio, o didžiausia jo įmanoma suma yra -1, gaunama pasirinkus posekį [4,-5]. 
5
2 -5 -5 -1 -2
 
1
 Ilgiausias įmanomas šokinėjantis posekis yra 2 elementų ilgio, o didžiausia jo įmanoma suma yra 1, gaunama pasirinkus posekį [2,-1]. 
5
1 -2 4 -1 -3
 
2
 Ilgiausias įmanomas šokinėjantis posekis yra 4 elementų ilgio, o didžiausia jo įmanoma suma yra 2, gaunama pasirinkus posekį [1,-2,4,-1]. Taip pat ilgiausias šokinėjantis posekis yra ir [1,-2,4,-3], tačiau jo suma yra mažesnė, todėl jis nėra atsakymas.