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

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

Условие

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

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

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

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

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

Ограничения

2 ≤ N ≤ 16

1 ≤ ai ≤ 106

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

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

0.035s 0.007s 15