Farmer John 的牛想像最喜欢的童谣中的牛一样跳过月亮。可惜牛不会跳。
当地巫医调制了 $P$ 份药水（$1 \le P \le 150{,}000$）帮助牛跳跃。必须严格按调制顺序服用，但可以跳过部分药水。
每份药水有增强跳跃能力的“强度”（$1 \le strength \le 500$）。奇数时间步服药增加跳跃高度，偶数时间步服药则降低高度。服用任何药水之前，牛的跳跃能力当然为0。
每份药水不能服用两次；一旦开始服药，就必须从时间1开始，每个时间步服用一份。每轮可以跳过一份或多份药水。
确定应服用哪些药水，以获得最高跳跃高度。
输入格式
- 第 $1$ 行：整数 $P$。
- 第 $2..P+1$ 行：每行包含一个整数，表示一份药水的强度。第2行是第一份的强度，第3行是第二份的强度，依此类推。
输出格式
- 第 $1$ 行：一个整数，表示最大可能跳跃高度。
样例
输入格式 1
8 7 2 1 8 4 3 5 6
输出格式 1
17