Задачі
Гiрки
Гiрки
Гіркою будемо називати неспадаючу послідовність з двох і більше чисел. Висотою гірки назвемо найбільший елемент у ній.
Гористим розбиттям послідовності назвемо набір з мінімальної кількості гірок, таких, що якщо їх записати по черзі зліва направо, отримаємо задану послідовність.
Вам дано набір чисел. Розмістіть їх у такій послідовності, щоб сума висот гірок у її гористому розбитті була максимальною.
Вхідні дані
Перший рядок вхідного файлу містить одне ціле число n - кількість чисел у наборі (2 ≤ n ≤ 100000). У другому рядку розміщено n цілих чисел в межах від 1 до 100000, відокремлених пропусками.
Вихідні дані
Вихідний файл повинен містити одне число - максимально можливу суму висот гірок у послідовності.
Приклад
Вхідні дані #1
4 1 2 3 4
Вихідні дані #1
7