B.寻找最大值

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 144 Accepted Submission(s) : 40

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

我们都知道RMQ -(范围最小/最大查询),我们可以用它来解决这样的问题是找到最小值在一个区间,例如,1、2、3、4、2、4、6第1、8,如果你想知道最小值在[1—7],
您可以使用RMQ来解决它在O(1)时间。但是现在,我想知道另一件。我们选择一个区间，合计这个区间的总价值,并将这个总价值乘以该区间中的最小价值。现在我要让这个值最大。聪明的你应该知道怎么做吧？

Input

第一行输入包含n(1 < = n < = 100000),接着n个数字

Output

针对每种情况,输出定义内的最大值

Sample Input

6
3 1 6 4 5 2
4
1 100 100 1

Sample Output

60
20000

Author

syu

Source

Developing School's Contest 6

Statistic | Submit | Back