P7482 Disorganized Rhapsody.

YSGHYYDS.

YSGH has a non-negative integer sequence $a$ of length $n$. Define $f(l, r)$ as the maximum possible sum of some pairwise non-adjacent numbers chosen from the subarray $[l, r]$ of sequence $a$. YSGH wants to know $\displaystyle \left[ \sum_{l = 1}^{n} \sum_{r = l}^{n} f(l, r) \right] \bmod ({10}^9 + 7)$.

The first line contains a positive integer $n$, denoting the length of the sequence. The second line contains $n$ non-negative integers $a_1, a_2, \ldots , a_n$.

Only one line containing one integer, denoting the answer.

**Sample Explanation** $f(1, 1)=1$, $f(1, 2)=2$, $f(1, 3)=5$, $f(2, 2)=2$, $f(2, 3)=4$, $f(3, 3)=4$. The answer is $1 + 2 + 5 + 2 + 4 + 4 = 18$. --- **Constraints** For $100\%$ of the testdata, $1 \le n \le {10}^5$, $0 \le a_i \le {10}^9$. - Subtask 1 (10 points): $n \le 500$. - Subtask 2 (20 points): $n \le 5000$. - Subtask 3 (20 points): $a_i \in \{ 0, 1 \}$. - Subtask 4 (20 points): $a_i \in \{ 1, x \}$, where $x$ is an integer greater than $1$. - Subtask 5 (30 points): No special constraints. Translated by ChatGPT 5