题目描述

皮卡丘是生活在野生群中的可爱电气鼠，拥有黄色皮毛和闪电尾巴，是深受喜爱的神奇宝贝。

乔小斯作为神奇宝贝的训练师，决定帮助皮卡丘组建一支队伍。

首先，乔小斯算出有神奇宝贝 $n$ 个。第 $i$ 个神奇宝贝的力量为 $a_i$。 作为一支军队，乔小斯可以选择任何非空的神奇宝贝子序列。

例如，乔小斯从 $a$ 数组当中选择了 $m$ 个神奇宝贝，对应 $m$ 个地址为 $b$ 数组，使得 $1≤b_1<b_2 <⋯<b_m≤n$，他的军队将由力量为 $a_{b1},a_{b2},…,a_{bm}$的神奇宝贝组成。

军队的力量等于子序列各数值的交替总和。即$a_{b1}-a_{b2}+a_{b3}-a_{b4}+...$。

帮助乔小斯实现他们的军队计划吧！

输入格式

第一行一个整数 $n$，表示神奇宝贝的数量。

第二行 $n$ 个整数 $a_i$，表示第 $i$ 个神奇宝贝的力量。

$1≤n≤10^4$，$1≤a_i≤10^5$。

输出格式

一行一个整数，表示军队力量的最大值

7 
2 2 5 4 3 6 7

9

提示

我们可以这样建立一支军队：[2 2 5 4 3 6 7]，其实力将是5−3+7=9.