eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Гiрки

Гiрки

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
4
1 2 3 4
Вихідні дані #1
7