Votre équipe de chasseurs de trésors vient de découvrir un site archéologique géant, rempli de métaux précieux et d'antiquités de valeur. Le site est composé de $n$ emplacements de fouille alignés.

Les plans initiaux suggèrent que chacun des $n$ emplacements de fouille est associé à un profit net. Le profit associé au $i$-ième emplacement est $p_i$. Plus précisément, cela signifie que votre équipe gagnerait $p_i$ dollars pour chaque mètre creusé dans le $i$-ième emplacement. Notez que $p_i$ peut également être négatif, ce qui signifie que le coût de fonctionnement des machines d'excavation dépasse le gain réel provenant du creusement dans le $i$-ième emplacement.

Naturellement, vous souhaitez creuser autant que possible dans les emplacements les plus rentables. Cependant, afin de ne pas provoquer de glissements de terrain, vous n'êtes pas autorisé à avoir des pentes trop raides. Plus précisément, pour deux emplacements adjacents quelconques, la différence entre la profondeur de creusement de ces emplacements ne peut pas différer de plus de 1 mètre. En particulier, les emplacements 1 et $n$ ne peuvent être creusés qu'à une profondeur maximale de 1 mètre.

Quel est le profit net le plus élevé que vous pouvez obtenir, sous ces conditions ?

Par exemple, un plan de fouille valide qui s'avère être optimal dans le cas de la première entrée d'exemple est illustré ci-dessous. Le profit net d'un tel plan est 8.

Entrée

La première ligne de l'entrée contiendra un entier positif $n$ ($1 \le n \le 250\,000$). La deuxième ligne de l'entrée contiendra $n$ entiers $p_i$ ($-10^6 \le p_i \le 10^6$), séparés par des espaces.

Sortie

Affichez exactement un entier, le profit le plus élevé que vous pouvez obtenir.

Exemples

Entrée 1

5
1 3 -4 2 1

Sortie 1

8

Entrée 2

4
1 1 -2 3

Sortie 2

5

Entrée 3

5
-1 -3 0 -5 -4

Sortie 3

0