该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

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

输入格式

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

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

输出格式

输出最大的分数。

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

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

样例输入

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

样例输出

73