题目背景

等待的玫瑰花 遗忘了来年花期

题目描述

给定一个序列 $\left\{a_{n}\right\}$，满足 $\forall i, a_{i} \geq 1$ 求一个区间 $[l, r]$ 使得其贡献 $\max _{l \leq i \leq r}\left\{a_{i}\right\} \times(r-l+1)-\sum_{l \leq i \leq r}\left\{a_{i}\right\}-(r-l+1)$ 最大。当然了，你也可以不选择，这样的贡献记为 $0$。

你不必输出这个区间，只需要输出他的贡献。

其中 $\max _{l \leq i \leq r}\left\{a_{i}\right\}$ 为对于 $i \in[l, r]$ 中 $a_{i}$ 的最大值。

$\sum$ 为求和符号，$\sum_{l \leq i \leq r}\left\{a_{i}\right\}$ 也可以写作 $a_{l}+a_{l+1}+\cdots+a_{r-1}+a_{r}$。

输入格式

第一行一个正整数 $n$。

接下来一行 $n$ 个正整数，表示 $\left\{a_{n}\right\}$。

输出格式

一行一个正整数，表示最大贡献。

样例 #1

5
1 3 2 4 5

5

提示

对于 $10\%$ 的数据，有 $n = 2$。

对于 $30\%$ 的数据，有 $n \leq 10^4$。

对于另外 $10\%$ 的数据，有 $a_i = i$。

对于 $100\%$ 的数据，有 $n \leq 10^6, 1 \leq a_i \leq 10^9$。