Problem description

Jasio wybrał się ze znajomymi na majówkę na Mazury. Ekipa podjęła decyzję żeby na wyprawę pojechać jego samochodem. Niestety, w trakcie podróży okazało się, że pogoda jest dość chłodna i Jasio rozważa teraz włączenie klimatyzacji aby podnieść temperaturę w pojeździe.

Układ klimatyzacji jest dość niewygodny w obsłudze. Składa się z N nawiewów ustawionych obok siebie. i-ty z nich ma moc M_i, czyli zwiększa temperaturę w pojeździe o dokładnie M_i stopni Bajcjusza. Czasami moc nawiewu może być ujemna i wtedy zmniejsza on temperaturę w samochodzie.

Na szczęście Jasio ma ze sobą dwie klapy. Dla~każdej z~nich może podjąć decyzję aby jej użyć lub nie. Użycie klapy polega na nałożeniu jej na wybrane przez siebie trzy kolejne nawiewy. Przykryte przez klapę nawiewy przestają zmieniać temperaturę.

Klapy mogą się nakładać na~siebie, ale jeżeli już zostaną użyte, to muszą w całości przykryć jakieś trzy sąsiednie nawiewy (nie jest na przykład możliwe przykrycie tylko dwóch pierwszych nawiewów lub ich częściowe przykrywanie).

Jasio zastanawia się o ile najwięcej stopni Bajcjusza jest w stanie podnieść temperaturę (jeżeli w ogóle opłaca mu się uruchomić klimatyzację).

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę nawiewów w samochodzie Jasia.

W drugim wierszu wejścia znajduje się N liczb całkowitych M_i oznaczających moce kolejnych nawiewów w samochodzie Jasia.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba całkowita oznaczająca największą możliwą liczbę stopni Bajcjusza, o które może wzrosnąć temperatura w samochodzie Jasia.

Ograniczenia

3 ≤ N ≤ 200 000,  − 1 000 000 ≤ M_i ≤ 1 000 000.

Przykład

6
-2 7 -1 -13 2 -7

5

6
-3 0 1000 -3 -6 2

997

8
-1 -1 -1 -1 -1 -1 -1 -1

0

3
2 0 23

25