Правила игры таковы: дана последовательность из N чисел. Игра
состоит из N-2 ходов. На каждом ходу из последовательности забирается одно
число. Брать можно любые числа, кроме первого и последнего. Если взято число
Ai, то ход приносит игроку Ai-1*Ai*Ai+1 очков, где Ai-1 - левый сосед числа
Ai, а Ai+1 - правый сосед. Игра заканчивается, когда в последовательности
остается два числа. Цель игры - набрать наибольшую сумму очков. Требуется по
заданной последовательности чисел определить, какую наибольшую сумму очков
может набрать игрок.
Формат входных данных:
В первой строке содержится натуральное N - количество чисел в последовательности,
2<=N<=100. Во второй (и, может быть, последующих) строках записаны N целых чисел из отрезка
[0,100]. Числа разделяются пробелами и/или символами конца строки.
Формат выходных данных:
Максимальная сумма очков.
Пример входных данных:
9
1 45 6 19 99 8 2 17 3
Пример выходных данных:
181676
|
