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