Processing math: 100%

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

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

Условие

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

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

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

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

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

Ограничения

2N16

1ai106

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

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

0.056s 0.008s 13