Problem description

Jasio dostał na urodziny zabawkę składającą się z N pól ułożonych w rzędzie. Pola są ponumerowane od 1 do N od lewej do prawej.

Wszystkie pola są początkowo puste. Jasio może wykonać dowolną liczbę operacji następujących typów, w dowolnej kolejności:

• Wybrać trzy sąsiednie puste pola i położyć na każdym z nich po jednym krasnalu.
• Wybrać trzy sąsiednie pola, z których każde zawiera po krasnalu, po czym zdjąć z tych pól te trzy krasnale.

Po wykonaniu wszystkich operacji Jasio dostaje A_i punktów, jeśli na i-tym polu stoi krasnal. Wynik Jasia to sumaryczna liczba punktów za pola z krasnalami.

Twoim zadaniem jest napisanie programu, który znajdzie maksymalną liczbę punktów jaką Jasio jest w stanie uzyskać.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N – liczba pól, z których składa się zabawka Jasia.

W każdym z kolejnych N wierszy znajduje się jedna liczba całkowita A_i – liczba punktów, jaką Jasio otrzyma, jeśli finalnie na i-tym polu będzie stał krasnal.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – maksymalny wynik, jaki Jasio może osiągnąć.

Ograniczenia

3 ≤ N ≤ 500,  − 100 ≤ A_i ≤ 100.

Przykłady

4
1
2
3
4

9

6
3
-2
-1
0
-1
4

6

10
-84
-60
-41
-100
8
-8
-52
-62
-61
-76

0