题目背景

DSES 在仓储管理中心工作，每周都要完成物资采购的规划工作。仓库的物资货架是一条直线排布的，货架上从左到右依次摆放着不同品类的物资，每一类物资如果进行批量采购，都可以获得一笔对应的收益数值。 仓储中心出台了严格的采购限制条例，为了避免单次采购占用过多仓储空间、造成货物堆积混乱，条例明确规定：不能同时采购两个位置相邻的物资。也就是说，如果 DSES 决定采购货架上第 $i$ 个位置的物资，那么它左边 $i-1$ 号位、右边 $i+1$ 号位的物资都不能纳入本次采购清单。 所有物资对应的采购收益都是正整数，没有收益为零或者亏损的物资。采购没有总件数限制，DSES 可以选择只采购一件，也可以挑选多件满足规则的物资，最终目标是让本次采购所有选中物资的收益相加总和达到最大值。现在需要编写程序，根据货架物资的数量与每件物资的收益，计算出 DSES 能够拿到的最大总收益。

输入说明

第一行输入一个正整数 $n$，代表货架上物资的总件数，物资按照从左至右顺序编号 $1~n$； 第二行输入 $n$ 个以空格隔开的正整数，依次对应第 $1$ 件到第 $n$ 件物资各自的采购收益。

输出要求

仅单独输出一行，该行只有一个整数，为 $DSES$ 能获取的最大采购总收益，无其他多余文字、符号。

数据范围：

$1 ≤ n ≤ 2000$ ，单件物资收益不超过 $10000$ 。

样例

6 
2 7 9 3 1 4

15

1 
36

36

3 
8 2 6

14

5 
5 1 2 7 3

12