Горки
Горкой будем называть неубывающую последовательность из двух и более чисел. Высотой горки назовем самый большой элемент в ней.
Гористым разбиением последовательности назовем набор из минимального количества горок, таких, что если их записать по очереди слева направо, получим исходную последовательность.
Вам дан набор чисел. Расположите их в такой последовательности, чтобы сумма высот горок в ее гористом разбиении была максимальна.
Технические условия
Входные данные
Первая строка входного файла содержит одно целое число n - количество чисел в наборе (2 ≤ n ≤ 100000). На второй строке расположено n целых чисел в пределах от 1 до 100000, разделенных пробелами.
Выходные данные
Выходной файл должен содержать одно число - максимально возможная сумма высот горок в последовательности.
Информация о задаче
Лимит времени: 2 секундыЛимит памяти: 64 MB
Баллы за пройденный тест: 5
Сложность: 62% 10/26
Пример
Пример входных данных4 1 2 3 4 |
Пример выходных данных7 |
| ← Опасный маршрут | Список задач | Синоптики → |