Składany kij składa się z $n$ odcinków o dodatniej długości. Odcinki są połączone zawiasami (rozciągliwymi sznurkami), dzięki którym można je złożyć o 180 stopni przy każdym zawiasie. Długością opakowania nazywamy długość kija po złożeniu go przy co najmniej jednym zawiasie. Może ona zależeć od sposobu składania.

Znajdź najmniejszą długość opakowania przy następującym sposobie składania: najpierw ułóż odcinki kija wzdłuż poziomej prostej. Następnie składaj kij zgodnie z ruchem wskazówek zegara, od lewej do prawej. Podczas składania odcinek przyczepiony po lewej stronie każdego zawiasu obraca się o 180 stopni zgodnie z ruchem wskazówek zegara albo nie obraca się wcale.

Na przykład poniższy rysunek pokazuje kij z czterech odcinków o sumie długości $10$. Długości od lewej do prawej wynoszą $3,2,2,3$, a zawiasy oznaczono ①, ②, ③.

W tym przykładzie kija nie można złożyć jednocześnie przy zawiasach ① i ②. Jeśli najpierw złożymy go przy ①, a następnie przy ②, odcinek długości $3$ przechodzący nad zawiasem ② zostanie złamany. Jeśli złożymy go tylko przy ②, długość opakowania wyniesie $5$. Jeśli złożymy go kolejno przy ① i ③, długość opakowania wyniesie $4$, jak na poniższym rysunku.

Dany jest ciąg długości odcinków składanego kija. Napisz program wypisujący jego najmniejszą długość opakowania.

Wejście

Program powinien czytać ze standardowego wejścia. Pierwszy wiersz zawiera liczbę całkowitą $n$ ($2\le n\le100000$), liczbę odcinków kija. Następny wiersz zawiera $n$ dodatnich liczb całkowitych opisujących długości odcinków od skrajnie lewego do skrajnie prawego. Długość każdego odcinka nie przekracza $20000$.

Wyjście

Program powinien pisać na standardowe wyjście. Wypisz dokładnie jeden wiersz zawierający dodatnią liczbę całkowitą oznaczającą najmniejszą długość opakowania.

Poniżej pokazano przykładowe wejście i wyjście dla trzech przypadków testowych.

Przykład

Wejście 1

4
3 2 2 3

Wyjście 1

4

Wejście 2

5
1 1 1 1 1

Wyjście 2

1

Wejście 3

7
1 3 2 3 4 2 2

Wyjście 3

6