有 N 个盘子，从左到右第 i 个盘子内放着 A_i 个橘子。你可以选择一组满足以下 3 个条件的整数 (l,r,x) ：

• 1\le l\le r\le N ；
• 1\le x ；
• 对于所有 l 以上 r 以下的整数 i ，x\le A_i 。

选择后，你会从第 l 到 r 个（包括两端）的盘子里面分别拿 x 个橘子吃。

计算当你选择了最优的一组整数 (l,r,x) ，可以吃到几个橘子。

• 第 1 行：一个正整数 N ；
• 第 2 行：N 个正整数，第 i 个正整数是 A_i 。

最多能吃几个橘子？

• 输入的全都是整数；
• 1\le N\le 10^4 ；
• 1\le A_i\le 10^5 。

样例 1 解释

当 (l,r,x)=(2,6,4) 时，可以吃 20 个橘子；

样例 2 解释

当 (l,r,x)=(1,1,200) 时，可以吃 200 个橘子。