题目背景

渴望成为魔女的小圆走进了一家神奇的魔法商店。店里有一排闪闪发光的宝物，每个宝物上都写着一个整数（可能是正数、负数，甚至零）。她不能随意打乱顺序，只能从左到右依次决定：拿，还是不拿。 这家店的招牌上写着奇怪的规则： 当你把选中的宝物按它们原本的顺序排好后，系统会自动给它们贴上“+”或“−”标签——第 $1$ 个是“+”，第 $2$ 个是“−”……以此类推，奇数位置加，偶数位置减。 最终，小圆的“总魔法值”就是这些带符号数字的总和。 小圆的目标很简单：在遵守顺序的前提下，挑选一部分宝物，使得她的最终的魔法值尽可能大！

题目描述

给定长度为 $n$ 的数组 ($a_1,a_2,\dots,a_n$)。从数组中保持原有相对顺序选取若干个元素组成一个新数组 ( $b_1,b_2,\dots,b_k$)，其中 $k$ 可以为 $0$ ,得分 $S$ 定义为：

$S=b_1-b_2+b_3-b_4+\cdots+(-1)^{k+1}b_k$

例如：

• 若有 $4$ 个数字：($S=b_1-b_2+b_3-b_4$)
• 若有 $3$ 个数字：($S=b_1-b_2+b_3$)

最大化得分 ( $S$ )。

子数组：从原数组中删除若干元素后，将剩余元素按原顺序拼接得到的数组。（即：子序列）

输入格式

• 第一行一个整数 $n$ ，表示宝物数量。
• 第二行 $n$ 个整数，表示每个宝物的数值。

输出格式

输出一个整数，表示最大可能的魔法值。

样例 #1

样例输入 #1

8
3 5 2 1 4 9 6 2

样例输出 #1

13

数据范围与提示

• 对于 $20$% 的数据：( $1 \le n \le 20$)。
• 对于另外 $20$% 的数据：保证数字全为正数，且序列单调不下降。
• 对于另外 $20$% 的数据：保证数字全为正数，且序列单调不上升。
• 对于 $100$% 的数据：$1 \le n \le 10^5,\quad -10^9 \le a_i \le 10^9$。