题目描述

中秋节快到了，徐老师得到了一份月饼清单，一共有 $n$ 个月饼排成一排，第 $i$ 个月饼的可口程度为 $a_i$。

现在徐老师需要从这一排月饼中选取其中的“一段”月饼，也就是说从 $1 \sim n$ 中选取两个数 $l,r(l < r)$，然后吃掉 $a_l,a_{l+1} \dots a_r$ 的月饼。

最后他会计算他的满意度 $S$：

1. 选从这段月饼中选出可口值最高的 $3$ 个月饼 $a_i, a_j, a_k$;
2. 满意度 $S = a_i + a_j + a_k - (r - l)$。

徐老师想知道，他应该怎么选取“一段”月饼，才能让这个满意度最大？

输入格式

第一行包含一个整数 $n$，表示月饼的个数；

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个月饼的可口值。

输出格式

一个整数，表示最大的满意度。

样例数据

输入样例1

5
5 1 4 2 3

输出样例1

8

解释：选择第 $1 \sim 5$ 个月饼，可以获得满意度：$5+4+3-(5-1)=8$，可以证明是最大的满意度。

输入样例2

10
5 8 17 5 8 5 7 8 10 9

输出样例2

30

数据范围

对于 $20\%$ 的数据， $3\le n \le 100$；

对于 $50\%$ 的数据， $3\le n \le 1000$；

对于 $100\%$ 的数据， $3 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^9$。