题目描述

一维消消乐是一款非常简单的游戏。有 n 颗珠子排成一排，每一颗珠子有一个价值 wi（可能是负数）。

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

输入格式

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

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

输出格式

输出最大的分数。

输入样例 #1

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

输出样例 #1

73

输入样例 #2

1
856

输出样例 #2

0

输入样例 #3

2
-707 794

输出样例 #3

0

数据范围

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

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