Под разрушенной башней археологи обнаружили ряд камней. На каждом высечено положительное целое число. Можно выбрать несколько пар соседних в исходном ряду камней. Для пары со значениями a и b восстанавливается a*b фрагментов.
a
b
a*b
Каждый камень можно использовать не более чем в одной паре. После выбора пары новые соседства не возникают: разрешены только пары камней, которые были соседними в исходном ряду.
Найдите максимальную суммарную величину по выбранным парам. Можно не выбирать ни одной пары.
В первой строке N (1 <= N <= 100000). Во второй строке N целых чисел от 1 до 10^6.
Выведите одно целое число — максимальную сумму.
4 5 6 7 5
65
4 1 100 100 1
10000
1500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач