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