ВШ 2019: паросочетания - Не только динамика!

Задача B. Не только динамика! ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

Дан набор a_i из N чисел. Необходимо расположить числа в последовательности a₁, a₂, …, a_N один за другим так, чтобы максимизировать следующую целевую функцию: (a₁ * a₂ + a₂ * a₃ + …  + a_N − 1 * a_N)

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

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

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

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

Ограничения

2 ≤ N ≤ 16

1 ≤ a_i ≤ 10⁶

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

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