题目描述

你有一个长度为 $n$ 的序列 $a$，它的一个区间 $[l,r]$ 的价值是

$$\max\{a_l,a_{l+1},\cdots,a_r\}-\min\{a_l,a_{l+1},\cdots,a_r\}-(r-l+1) $$

求这个序列价值最大的子区间并输出这个价值。

输入格式

第一行输入一个正整数 $n$，表示笔记的章节数。

第二行输入评价分序列 $a$，以空格隔开每一个元素。

• 对于 $20\%$ 的数据，$n\leq 5\times 10^3$。
• 另有 $20\%$ 的数据，所有的 $a_i$ 都相等。
• 对于 $100\%$ 的数据，$1\le n\le 4\times10^6$，$1 \leq a_i \leq 10^9$。

输出格式

输出这个评价分序列中，老师满意度最大的子区间的满意度。

样例

6
5 2 4 2 8 8

4

令 $l=4,r=5$，则有 $\min\{a_4,a_5\}=2$，$\max\{a_4,a_5\}=8$，贡献值为 $4$。易证这是满意度最大的子区间。