Problem5207--古玩商家

5207: 古玩商家

Time Limit: 1.000 Sec  Memory Limit: 256 MB
Submit: 37  Solved: 22
[Submit] [Status] [Web Board] [Creator:]

Description

你是一位古玩商家,现在有N(1≤N≤2000)个古玩.每天你售出一个古玩.当然你希望这些古玩全部售出
后能得到最大的收益.这些古玩有以下这些有趣的特性:
•古玩按照1...N
编号,它们被排成一列放在一个很长的盒子里.盒子的两端都有开口,你每天可以从盒
子的任一端取出最外面的一个.
•古玩储存得越久价值越高.当然,这样你就可以把它们卖出更高的价钱.
•每瓶古玩的初始价值不一定相同.你进货时,第 个古玩的初始价值为V_i(1<=V_i<=1000)
•第 i个古玩如果在被买进后的第 a天出售,则它的售价是a*V_i
希望你计算一下,在这些古玩全被卖出后,你最多能得到多少钱.

Input

第一行一个整数N
接下来包含N 行,每行一个整数,代表古玩的初始价格

Output

一个整数代表代表最多能得到的钱

Sample Input

5
1
3
1
5
2

Sample Output

43

HINT


Source/Category

 

[Submit] [Status]