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

Горки

Горки

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

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

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

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

Входные данные

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

Выходные данные

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

Пример

Входные данные #1
4
1 2 3 4
Выходные данные #1
7