Description

给定一个序列 $a_1, a_2, \ldots, a_n$。

你需要选择 $a$ 中的零个或多个元素，使得：如果你选择了 $a_i$，那么在任何长度为 $i$ 的区间内（形式上，对于任何 $1 \le j \le n - i + 1$ 的 $a[j, j + i - 1]$），最多可以选择 $2$ 个元素。

计算你选择的元素的最大和。

Input Format

第一行包含一个整数 $n$ ($2 \leq n \leq 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$)。

Output Format

输出一个整数，表示答案。

4
1 4 3 2

7

3
-10 -10 -10

0

Hint

来源：2022 ICPC 亚洲西安区域赛问题 J。

作者：JohnVictor。

题面翻译由 ChatGPT-4o 提供。