Problem Description

小L最近迷恋上一了一款游戏，为了这款游戏他氪了不少金，但是事实证明他就是个非酋。这个游戏有个良心（kengdie）的抽奖系统：它会显示一排瓦罐，玩家可以选择敲击其中的任何一个瓦罐，一旦选择敲碎某个瓦罐，跟它相邻且价值大于或者等于他的瓦罐的都会被敲碎，但是只能够获得敲碎瓦罐的价值，比如说现在有4个瓦罐，它们的价值分别为5,4,1,3，假设你现在敲碎价值为1的瓦罐，那所有瓦罐都会被敲碎，获得的收益为1x4=4，但是如果你敲碎价值为4的瓦罐，第一个和第二个瓦罐会被敲碎，获得的价值为2x4=8。现在小L通过某种渠道获得所有瓦罐的价值，请你帮他求出他能获得的最大收益为多少？

Input

有多组测试数据，每组数据输入一个n(1<=n<=100000), 代表瓦罐的个数，紧接着有n个数，代表每个瓦罐的价值wi(1<=wi<=10000)

Output

每组数据输出一行，输出小L获得的最大收益

Sample Input

4
5 4 1 3

Sample Output

8

Author

zhbit_acmer