题目描述

你是一名海盗，根据藏宝图来到一座荒岛。在山洞中，你看到一排共 $n$ 个宝箱，从左到右依次编号为 $1,2,\dots,n$。第 $i$ 个宝箱中宝物的价值为 $a_i$。

所有宝箱都未被打开过。你可以选择打开其中任意若干个宝箱并取走宝物，但不能改变宝箱的位置或顺序。然而，这些宝箱受到了诅咒：一旦你打开某个宝箱并取走其中的宝物，与它左右相邻的宝箱中的宝物就会立刻消失。换言之，你不能同时取走两个相邻宝箱中的宝物。

求：你能够取走的宝物的最大总价值。

输入格式

第一行，一个整数 $n$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，以空格分隔。

输出格式

输出一个整数，表示你能够取走的宝物的最大总价值。

样例

5
4 2 3 9 5

13

7
1 2 3 4 5 6 1

12

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 1000, a_i \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5, 1 \le a_i \le 10^9$