P9367 [ICPC 2022 Xi'an R] Strange Sum

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

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

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

**来源**：2022 ICPC 亚洲西安区域赛问题 J。 **作者**：JohnVictor。 题面翻译由 ChatGPT-4o 提供。