题目描述

你在玩一个寻宝类游戏，一共有 $n$ 个格子，编号为 $1 \sim n$，你每在 $i$ 号格子上下挖一层便会获得 $p_i$ 的价值，其中你需要保证每个格子相邻的两个格子都与其下挖的深度的差值不超过 $1$（注意此时 $1$ 和 $n$ 号点最多只能挖一层），请最大化总价值。

输入格式

第一行一个整数 $n\ (1 \leq n \leq 2.5 \times 10^5)$。

接下来一行 $n$ 个整数 $p_i\ (-10^6 \leq p_i \leq 10^6)$。

输出格式

输出最大价值。

5
1 3 -4 2 1

8

4
1 1 -2 3

5

5
-1 -3 0 -5 -4

0

提示

样例一解释：