题目描述

Farmer John 的奶牛们想要像它们最喜欢的童谣里的奶牛一样跳过月亮。不幸的是，奶牛们并不会跳跃。 当地的巫医调制了 P（1 ≤ P ≤ 150,000）种药水来帮助奶牛完成跳跃的目标。这些药水必须严格按照它们被制作的顺序服用，但有些药水可以跳过不服用。 每种药水都有一个 “强度” 值（1 ≤ 强度 ≤ 500），用于增强奶牛的跳跃能力。在奇数时间步服用药水会增加奶牛的跳跃能力；在偶数时间步服用药水会减少跳跃能力。在服用任何药水之前，奶牛的跳跃能力当然是 0。 每种药水只能服用一次。一旦奶牛开始服用药水，就必须从时间步 1 开始，在每个时间步服用恰好一剂药水（可以跳过若干药水，但每个时间步必须选择当前未服用的下一个或多个药水来服用，且每个时间步只能服用一剂）。 请确定应该服用哪些药水，以使得奶牛的跳跃能力达到最大值。

输入格式

第 1 行：单个整数 P

第 2 到 P+1 行：每行一个整数，表示一种药水的强度。第 2 行对应第一种药水的强度，第 3 行对应第二种，依此类推。

输出格式

第 1 行：单个整数，表示可能的最大跳跃能力值。

输入输出样例

输入数据 1

8

7

2

1

8

4

3

5

6

输出数据 1

17