Сжатие данных
Нурбакыт начал уставать от работы разработчика и решил, что ему нужно хобби. Компьютерные игры слишком брутальны, а вышивка слишком дорога. Он начал заниматься музыкой, но все звучало как «Дарудэ - Песчаная буря».
После нескольких недель борьбы он наконец нашел то, к чем мог бы заняться. Нурбакыт начал участвовать в турнирах по алгоритмической торговле. Он использует машинное обучение для построения прогнозируемых моделей.
Обычно набор данных Nurba выглядит как массив из n чисел. Массив слишком велик для выполнения любого алгоритма глубокого обучения. Нурбакыт решил, что ему нужно сжать массив чисел. Просматривая форумы, он обнаружил алгоритм сжатия, известный как "бессмысленное сжатие". Алгоритм разбивает массив на несколько сегментов и заменяет сегмент парой из двух наибольших чисел в нем. Пользователь по имени ElonMusk228 предполагает, что статистическая ошибка сжатия зависит от суммы этих двух чисел для каждого сегмента. Нурбакыт хочет протестировать алгоритм "бессмысленного сжатия", поэтому ему нужна программа, которая разбивает массив, минимизируя сумму произведений двух наибольших чисел в каждом сегменте.
Обратите внимание, что для сжатия массива каждый сегмент должен содержать как минимум два числа.
Входные данные
Первая строка содерит одно целое число n (2 ≤ n ≤ 10^6).
Вторая строка содержит n чисел a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^6) - массив Нурбакыта.
Выходные данные
Выведите одно целое число - минимальную сумму произведений пар после сжатия.