UOJ Logo

NOI.AC

1S 512MB

#1597. 消消乐

Statistics

题目描述

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

游戏是这样,你可以选择如若干对相邻的珠子,让他们同时消去。每一对珠子的消失,都会使得总分数加上两颗珠子相乘的分数。

注意,每个珠子只能消一次,并且珠子消去以后,还会占位。

输入格式

输入第一行一个整数$n(1 \leq n \leq 10000)$。 接下来一行输入 $n$ 个整数 $(−1000 \leq w_i \leq 1000)$。

输出格式

输出最大的分数。

样例输入:

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

样例输出:

73