Problem 2611 --城墙攻防战 wall

2611: 城墙攻防战 wall

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][4308kb]

Description

南山中学的校长对于绵中称霸数理化生竞赛很不爽,于是派出他们引以为豪的信奥班来攻打绵中的城墙。这项防御任务自然就落到了绵中信奥班的同学们身上。

已知绵中的城墙是由线性排列的N个石块组成,排列由1N,每个石块都有它的防御值ai,由许多石块连成一段的城墙的防御值等于这段城墙内所有石块防御值之和乘以这段城墙内防御最低的那块石头的防御值。

经过战术商讨,绵中信奥班决定将敌人引入一段防御最高的城墙将其全歼,但是寻找出这段防御最高的城墙的问题需要他们快速解决。

Input

两行:

第一行一个正整数 N,表示城墙石块的个数。

第二行N个整数,表示每个石块的防御值。

Output

一行:

最强防御的城墙的防御力。


Sample Input

6
3 1 6 4 5 2

Sample Output

60

HINT








20% 0<=n<=1000;



100% 0<=n<=100000,0<=ai<=1000000.





Source

[Submit][Status]