题目描述

A 国和 B 国积怨已久，战争不可避免的爆发了，在一次战役中，A 国的一支部队包围了 B 国的一座城池，就在 A 国以为胜利在望的时候，却殊不知 B 国正在计划利用坚固的城墙进行反击。
已知 B 国城池的城墙是由线性排列的 N 个石块组成，排列由 1 到 N，每个石块都有它的防御值 \(a_i\)，由许多石块连成一段的城墙的防御值等于这段城墙内所有石块防御值之和乘以这段城墙内防御最低的那块石头的防御值。
经过战术商讨，B 国决定将敌人引入一段防御最高的城墙将其全歼，但是寻找出这段防御最高的城墙的问题需要他们快速解决。

输入格式

第一行一个正整数 N，表示城墙石块的个数。
第二行 N 个整数，表示每个石块的防御值。

输出格式

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

样例输入

6
3 1 6 4 5 2

样例输出

60

数据范围

对于 20%的数据 0 \(\leq\) n \(\leq\) 1000；
对于 100%的数据 0 \(\leq\) n \(\leq\) \(10^5\), 0 \(\leq\) \(a_i\) \(\leq\) \(10^6\)。

限制

1s

来源

CWOI新高二专题测试十⑨