問題文

長さが $N$ の数列 $A$ が与えられます。

空でない数列 $B$ に対するスコアを以下のように定義します。

• $B$ の長さを $K$ とすると、スコアは $\displaystyle \sum_{i = 1}^{K} B_i \times (-1)^{i}$

あなたは、$A$ の空でない連続とは限らない部分列を $1$ つだけ選び、その部分列に対するスコアを得ることができます。

あなたが得られるスコアとしてありうる最大値を求めてください。

制約

• $1 \leq N \leq 2 \times 10^{5}$
• $| A_i | \leq 10^{9}$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1$ $A_2$ ... $A_{N}$ 

出力

問題の答えを一行に出力せよ。

サンプル

5
-3 -2 1 2 3

6

8
-887791923 -540126285 688481141 -734932412 -109240649 225669457 786200001 72702954

3097405477