Игра «Палиндромика» набирает все большую популярность в казино Рулеттенбурга. Правила «Палиндромики» довольно просты: в начале игры на листок записывается строка и игроки поочередно стирают первый или последний символ. Побеждает игрок, перед ходом которого строка представляет собой палиндром. Палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево.

Алексей Иванович — азартный игрок, однако вместо участия в игре предпочитает делать ставки. Ему удалось узнать, какая строка будет предложена для игры. Алексею Ивановичу предсказать исход игры при оптимальных действиях обоих игроков не под силу. За помощью он обратился к вам.

Дана последовательность чисел a₁, a₂, ..., a_n. За одну операцию разрешается удалить любое (кроме крайних) число, заплатив за это штраф, равный произведению этого числа на сумму соседних. Требуется удалить все числа, кроме крайних, с минимальным суммарным штрафом.

Пример начальной последовательности:

1 50 51 50 1

удаляем четвертое число, штраф 50·(1 + 51) = 2600, получаем

1 50 51 1

удаляем третье число, штраф 51·(50 + 1) = 2601, получаем

1 50 1

удаляем второе число, штраф 50·(1 + 1) = 100.

Итого, штраф 5301.

На аллее перед зданием Министерства Обороны в ряд высажены n дубов. В связи с грядущим приездом главнокомандующего, было принято решение срубить несколько деревьев для придания аллее более милитаристического вида.

Внутренние распорядки министерства позволяют срубать дуб только в двух случаях:

• если и ближайший дуб слева, и ближайший дуб справа строго ниже, чем данный дуб;
• если и ближайший дуб слева, и ближайший дуб справа строго выше, чем данный дуб.

В частности, согласно этому правилу, нельзя срубить крайний левый и крайний правый дубы.

Министр хочет выработать такой план вырубки, чтобы в итоге осталось несколько дубов, высоты которых образуют неубывающую последовательность, то есть чтобы каждый дуб был не ниже, чем все дубы, стоящие слева от него. При этом, как человек любящий флору, министр хочет, чтобы было срублено минимальное возможное количество деревьев.

Помогите сотрудникам министерства составить оптимальный план вырубки аллеи или выяснить, что срубить дубы соответствующим образом невозможно.

В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от неё. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остаются только эти две карты.

Цель игры — убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.

Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки 10·1·50 + 50·20·5 + 10·50·5 = 500 + 5000 + 2500 = 8000. Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким: 1·50·20 + 1·20·5 + 10·1·5 = 1000 + 100 + 50 = 1150.