题目描述

有 $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$ 。

N
A(1) ... A(N)

输出格式

高桥君最多能吃几个橘子？

数据范围

• 输入的全都是整数；

• $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$ 个橘子。