题目背景

Special for beginners, ^_^

题目描述

有 n 个格子排成一排，每个格子里有一个整数 ai。

你从 左到右扫描这些格子，每次有两个选择：

选择收集当前格子的数字，累计到你的分数，然后 跳过下一个格子（不能收集下一个格子）。

选择不收集，直接移动到下一个格子。

你只能往右走，每个格子最多考虑一次。

求 你能获得的最大分数。

输入格式

第一行输入整数 n。

第二行输入 n 个整数：

a1 a2 ... an

数据范围 1 ≤ n ≤ 2e5 -1e9 ≤ ai ≤ 1e9

输出格式

输出一个整数，表示 最大可获得分数。

样例

5
1 2 9 4 5

15

样例解释

可以这样选择：

收集第 1 个格子（1），跳过第 2 个 → 分数 = 1

收集第 3 个格子（9），跳过第 4 个 → 分数 = 1 + 9 = 10

收集第 5 个格子（5） → 分数 = 10 + 5 = 15

最大分数 = 15