Задача F. Не только динамика! Новые тесты!

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Дан набор ai из N чисел. Необходимо расположить числа в последовательности a1, a2, …, aN один за другим так, чтобы максимизировать следующую целевую функцию: (a1 * a2 + a2 * a3 + …  + aN − 1 * aN)

Формат входного файла

Входной файл содержит N, за которым следует N чисел ai.

Формат выходного файла

В выходном файле единственное число - максимальное значение целевой функции.

Ограничения

2 ≤ N ≤ 16

1 ≤ ai ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
9 1 9 2
108

0.074s 0.009s 13