暂无测试数据。

看到你这么快地解决了提出的问题，小蒜非常的着急。

虽然你让他别急，但是他还是很急，因此他给出了一个困难的区间问题。

形式化题意：

给定一个长度为 $n$ 的正整数序列 $a$，定义一个区间 $[l,r]$ 的分值为 $(\max_{l\le i\le r}a_i)\times(r-l+1)-\sum_{l\le i\le r}a_i-(r-l+1)$。求所有非空子区间的最大分值。

输入格式

第一行一个正整数 $n$，表示数列的长度。

接下来一行 $n$ 个正整数 $a_i$，描述这个数列。

输出格式

输出一个整数，表示答案。

数据范围

• 对于 $50\%$ 的数据，$n\le 10^3$。
• 对于另外 $50\%$ 的数据，没有特殊限制。
• 对于 $100\%$ 的数据，$1\le n\le 10^6,1\le a_i\le 10^9$。

5
1 2 3 4 5

5

5
1 2 1 2 1

-1