Гiрки

Гіркою будемо називати неспадаючу послідовність з двох і більше чисел. Висотою гірки назвемо найбільший елемент у ній.

Гористим розбиттям послідовності назвемо набір з мінімальної кількості гірок, таких, що якщо їх записати по черзі зліва направо, отримаємо задану послідовність.

Вам дано набір чисел. Розмістіть їх у такій послідовності, щоб сума висот гірок у її гористому розбитті була максимальною.

Вхідні дані

Перший рядок вхідного файлу містить одне ціле число n - кількість чисел у наборі (2 ≤ n ≤ 100000). У другому рядку розміщено n цілих чисел в межах від 1 до 100000, відокремлених пропусками.

Вихідні дані

Вихідний файл повинен містити одне число - максимально можливу суму висот гірок у послідовності.

Приклади