区间DP专栏 第一章（双色马、神医胡青牛、Deque等）

#A.神医胡青牛

题目描述

胡青牛是“倚天屠龙记”中的神医（但从此题目看出很贪财），每天都有N多(N<=2000)的人来求他治病，这些人排成一队，从1开始编号直到N
,每个人手里都拿着一个牌子,其上的值用Ai(1<=i<=N,1<=ai<=1000)代表，表示自己愿意付给胡大牛多少钱做为酬
金。胡神医每次从队首或队尾取一个人出来，治完这个人之后，他将获得M*Ai的Money其中M代表这个病人是第几个
被救治的。 

输入格式

如题

输出格式

如题

样例

输入数据 1

5
1
3
1
5
2

Copy

输出数据 1

43
Hint
胡大牛将按1, 5, 2, 3, 4的顺序来治人,赚得1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.

 解题思路

（虽然这黑心