#Z5016. 一维消消乐

一维消消乐

一维消消乐是一款非常简单的游戏。有 n 颗珠子排成一排,每一颗珠子有一个价值 wiw_i(可能是负数)。

游戏是这样,你可以选择如若干对相邻的珠子,让他们同时消去。每一对珠子的消失,都会使得总分数加上两颗珠子相乘的分数。注意,每个珠子只能消一次,并且珠子消去以后,还会占位。

输入格式

输入第一行一个整数n(1≤n≤10000)。

接下来一行输入 n 个整数 wi(-1000≤wi≤1000)。

输出格式

输出最大的分数。

输出时每行末尾的多余空格,不影响答案正确性

要求使用「文件输入输出」的方式解题,输入文件为 happy.in,输出文件为 happy.out

样例输入

8
-9 -5 -4 -2 4 -5 -4 2

样例输出

73

Statistics

Related

In following contests:

3月9日周六8:10

3月9日周六8:10

In following homework:

递推(简单dp)