P9367 [ICPC 2022 Xi'an R] Strange Sum

Given a sequence $a_1, a_2, \ldots, a_n$. You are going to select zero or more elements of $a$ so that: if you select $a_i$, then in any interval of length $i$ (formally, in $a[j, j + i - 1]$ for any $1 \le j \le n - i + 1$) you can select at most $2$ elements. Calculate the maximal sum of the elements you select.

无

无

**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem J. **Author**: JohnVictor.