该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Self-deception

时间限制：1000ms

空间限制：256MB

背景描述

Monster是一个巨特么菜的计算机学子，一年中他参加了不少程序设计比赛，但是都成绩惨淡。

所以，Monster下定决心开始刷题提升自己！

题目描述

在接下来的$n$天里，趁着Monster的刷题激情还没消退，Monster在会每天刷一道价值为$value$的题目。贴心的YQJ给Monster已经规划好了刷题计划，所以所有题目的$value$值将会全部给出。

但是，显然Monster是不会好好刷题的 （因为他真是大懒狗天天只想打瓦），所以Monster决定偷懒。他认为他只需要刷其中价值最高的两题就可以了，但是考虑到刷题的间隔太长会导致刷题效果降低，所以他经过胡乱猜想列出了这样一个价值计算公式。

$$FinalValue = max(value[i] + value[j] + i - j)$$

其中 $0 \leq i < j <n$

也就是说最终价值等于这两天刷的题目价值之和减去相差的天数，这样只要使得最终的$FinalValue$最大，Monster就觉得完成任务了。（纯掩耳盗铃行为，别学）

输入格式

第一行包含一个整数$n$，表示Monster的刷题将会持续$n$天。

接下来$n$行，第$i$行有一个值$value[i]$，表示第$i$天Monster将会刷的题目的价值$value$。

输出格式

输出包括两行，第一行一个数$FianlValue$表示Monster认为的最大价值。

样例输入1

5
1
2
3
4
5

样例输出1

8

样例1解释

从第0天开始，刷第3天的题可以获得的价值为4，刷第4天的题可以获得的价值为5，可以证明此时FinalValue最大，为4 + 5 + 3 - 4 = 8.

数据范围及约定

对于 $60\%$ 的数据，$2 \le n \le 10, 0 \le value[i] \le 10^3$。

对于 $100\%$ 的数据，$2 \le n \le 10^6, 0 \le value[i] \le 10^5$。