Problem description

Krasnal Fontanek troszczy się o dobry stan wrocławskich fontann. Niedawno wyłowił z nich N monet (oczywiście wyłącznie po to, aby nie zapychały odpływów). Wartość i-tej monety wynosi W_i złotych.

Fontanek chce podzielić zebrane monety między swoich dwóch synów — starszego Grosika oraz młodszego Miedzika. Uznał jednak, że dzieci nie powinny dostać wszystkich pieniędzy naraz, więc postanowił wypłacać im kieszonkowe.

Przez najbliższe $\frac{N}{2}$ tygodni każdego tygodnia przekaże każdemu z synów po jednej monecie. Każda moneta zostanie rozdana dokładnie raz.

Jeżeli w danym tygodniu przekazane monety mają różne wartości, droższą monetę zawsze otrzyma starszy syn, czyli Grosik. Jeśli obie monety mają tę samą wartość, Fontanek może rozdać je dowolnie.

Miedzika zadowoli nawet mniejsze kieszonkowe — w końcu wydatki pięciolatka ograniczają się głównie do lodów od czasu do czasu. Mimo tego Fontanek chciałby, aby Miedzik czuł się potraktowany możliwie sprawiedliwie. Dlatego zależy mu na tym, aby łączna wartość monet otrzymanych przez młodszego syna była jak największa (a więc jak najbardziej zbliżona do kwoty otrzymanej przez Grosika).

Pomóż Fontankowi obliczyć maksymalną sumę wartości monet, jaką może otrzymać Miedzik.

Wejście

W pierwszym wierszu wejścia znajduje się jedna parzysta liczba całkowita N — liczba wyłowionych monet.

W drugim wierszu znajduje się N liczb całkowitych W₁, W₂, …, W_N oznaczających wartości kolejnych monet.

Wyjście

W pierwszym (jedynym) wierszu wyjścia należy wypisać jedną liczbę całkowitą — maksymalną możliwą łączną wartość monet otrzymanych przez Miedzika.

Ograniczenia

2 ≤ N ≤ 100 000, 0 ≤ W_i ≤ 10⁹.

Przykłady

6
1 2 10 5 7 4 

12

2
1 1000000000

1

4
5 5 5 5

10