题目描述

小可爱最近学了数组，迷上了一个序列问题。

给定一个序列 $A$，包含 $n$ 个正整数，第 $i$ 个正整数表示为 $a_i$。需要从序列 $A$ 中选择若干个数字，按照 $A$ 序列中的原顺序依次排列组成一个新的序列 $B$。

序列 $B$ 的值定义为：奇数位置上的数字之和减去偶数位置上的数字之和（位置从 $1$ 开始计数）。

问题是在给定序列 $A$ 的情况下询问序列 $B$ 的最大值。

输入格式

第一行一个正整数 $n$，表示序列 $A$ 共有 $n$ 个数字。

每二行包含 $n$ 个正整数。

输出格式

输出序列 $B$ 的最大值。

样例1

输入

3
3 1 2

输出

4

解释

取 3 1 2

样例2

输入

5
5 4 1 2 3

输出

7

解释

取 5 1 3

数据规模与约定

• 对于 30% 的数据，$1\le n \le 20$。
• 对于 60% 的数据，$1\le n \le 1000$。
• 对于 100% 的数据，$1\le n \le 100000，1 ≤ a_i ≤ 1000000$。