reduceri

Да разгледаме редица от N различни цели положителни числа x1, x2, ... xN. Премахването на p на брой числа от редицата, всичките намиращи се или в началото на редицатат или в нейния край, наричаме p-редукция. С други думи, една p-редукция се състои или в премахване на елементите x1, x2, ...,xp, или в премахване на xN-p+1, xN-p+2, ..., xN. Очевидно, след редукцията редицата става по-къса с p елемента.

Към редица, получена след редукция може да се приложи нова редукция или последователност от редукции с различни дължини. Това може да се повтаря, докато редицата не е празна.

Цената на една редукция се пресмята като абсолютната стойност на разликата между елементите от краищата на премахнатата подредица, умножена по броя на премахнатите елементи. Например, ако редукцията е премахнала xi, xi+1, ..., xk, тогава цената й е |xixk|*(i-k+1). В случая, когато редукцията е с дължина 1, цената й е равна на стойността на премахнатия елемент. Общата цена на последователност от редукции е равна на сумата от цените на всичките редукции.

Задача

Определете максималната цена на всички редукции, които могат да се приложат последователно към дадена редица.

Вход

Входният файл reduceri.in съдържа в първия си ред едно цяло положително число N. На следващия ред е записана дадената редица, състояща се от N различни цели положителни числа.

Изход

Файлът reduceri.out трябва да съдържа един ред, на който е записана общата максимална цена, получаваща се при прилагането на последователност от редукции върху дадената редица.

Ограничения и пояснения

3<=N<=100
Елементите на дадената редица са различни строго положителни цели числа от интервала 1..1000.
Възможно е и прилагането на една единствена редукция, с която се премахва цялата дадена редица.

Промер

reduceri.in

reduceri.out

Обяснение

6
54 29 196 21 133 118

768

Трябва да се направят 3 редукции. Първата редукцията премахва първите 3 елемента на цена 426. Втората редукция премахва последния елемент на цена 118. Третата редукция премахва всичко, което е останало от редицата, а именно 21 и 133, и има цена 224. Общата цена е 426+118+224=768

Време за работа на програмата: 0.1 сек.за тест

prof. Dan Pracsiu
Industrial School Group һtefan ProcopiuVaslui
Contact: dpracsiu@yahoo.com

Превод на български: Емил Келеведжиев