Description

由于前两天都被莲子用来进行活动的筹备工作了，所以现在她只有几分钟的时间糊弄作业。尽管这样不太好，但是她别无选择，只能从之前的课堂笔记中摘取一段内容。

莲子的课堂笔记共有 $n$ 章，每章分别记着不同的内容。她可以选择其中任意连续的一段 $[l,r]$（表示选取了第 $l$ 章到第 $r$ 章）作为最终的成果。

每一章的内容各不相同，老师对每章内容有一个评价分 $a_i$。因为学习报告要体现出学生的进步，所以老师的满意度将会加上其中最差（$\min\{a_i\}$）和最好章节（$\max\{a_i\}$）的评价分差距。因为直接把冗长的课堂笔记作为报告提交显得太敷衍，所以每存在一章内容，老师的满意度就会 $-1$。

形式化地来说，如果莲子提交了 $[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$，它的一个区间 $[l,r]$ 的价值是 $\max\{a_l,a_{l+1},\cdots,a_r\}-\min\{a_l,a_{l+1},\cdots,a_r\}-r+l-1$。求这个序列价值最大的子区间并输出这个价值。

Input Format

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

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

Output Format

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

6
5 2 4 2 8 8

4

Hint

【样例解释和说明】

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

【数据范围】

• 对于 $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$。