Twój zespół poszukiwaczy skarbów właśnie odkrył ogromne stanowisko archeologiczne, pełne metali szlachetnych i cennych antyków. Stanowisko składa się z $n$ miejsc wykopalisk położonych w linii.

Wstępne plany sugerują, że każde z $n$ miejsc wykopalisk ma przypisany zysk netto. Zysk przypisany do $i$-tego miejsca wynosi $p_i$. Dokładniej oznacza to, że Twój zespół zyska $p_i$ dolarów za każdy metr wykopany w $i$-tym miejscu. Zauważ, że $p_i$ może być również ujemne, co oznacza, że koszt eksploatacji maszyn wydobywczych przewyższa rzeczywisty zysk z kopania w $i$-tym miejscu.

Naturalnie, chciałbyś kopać jak najwięcej w najbardziej dochodowych miejscach. Jednak, aby nie spowodować osunięć ziemi, nie możesz tworzyć zbyt stromych zboczy. Dokładniej, dla każdych dwóch sąsiednich miejsc, różnica głębokości wykopów w tych miejscach nie może przekraczać 1 metra. W szczególności, miejsca 1 oraz $n$ mogą być wykopane na głębokość co najwyżej 1 metra.

Jaki jest największy zysk netto, jaki możesz uzyskać przy tych warunkach?

Na przykład, poprawny plan wykopalisk, który okazuje się optymalny w przypadku pierwszego przykładu, został zilustrowany poniżej. Zysk netto takiego planu wynosi 8.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą dodatnią $n$ ($1 \le n \le 250\,000$). Druga linia wejścia zawiera $n$ liczb całkowitych $p_i$ ($-10^6 \le p_i \le 10^6$), oddzielonych spacjami.

Wyjście

Wypisz dokładnie jedną liczbę całkowitą, największy zysk, jaki możesz uzyskać.

Przykład

Wejście 1

5
1 3 -4 2 1

Wyjście 1

8

Wejście 2

4
1 1 -2 3

Wyjście 2

5

Wejście 3

5
-1 -3 0 -5 -4

Wyjście 3

0