Podciąg Jasia

To zadanie pochodzi z Kółka Informatycznego w Staszicu.

Jaś ma swój ciąg. Ale ciąg Jasia zaczął się nudzić. Dlatego Jaś chce wybrać taki (niespójny) kawałek ciągu, który się nie będzie nudził i jednocześnie Jaś będzie go bardzo lubił (jego suma będzie maksymalna). Element nowego podciągu nudziłby się, gdyby miał takiego samego sąsiada jak wcześniej. Żaden element nowego podciągu nie może się nudzić.

Wejście, wyjście

W pierwszej linii wejścia znajdują się liczba n (1 <= n <= 1000000), n oznacza długość ciągu Jasia. W drugiej linii znajduje się n współczynników lubienia -10⁹ < x_i < 10⁹ oddzielonych spacjami. Każdy z nich oznacza jak bardzo Jaś lubi i-ty element ciągu (1000000000- bardzo lubi, -1000000000 - nienawidzi). Na wyjściu powinieneś wypisać jedną liczbę - sumę współczynników lubienia dla najlepszego podciągu.

Przykład

Dla danych wejściowych:

4
10 1 1 10

Poprawną odpowiedzią jest:

20

Najlepszym podciągiem będzie 10, 10