题目描述

小可在探险时发现了一条古老的走廊，走廊尽头依次摆放着 $n$ 颗魔法石，编号为 $1$ 到 $n$。每颗魔法石都蕴含着神秘的能量，第 $i$ 颗石头的能量值为 $a_i$（可能为正、负或零）。

小可必须按顺序经过这些石头，对于每一颗石头他可以选择拾取或跳过。被拾取的石头会按拾取顺序形成一串项链。然而魔法石之间会产生奇妙的共鸣：

• 若一颗石头是第 奇数 次被拾取，它释放出原本的能量值；
• 若一颗石头是第 偶数 次被拾取，它的能量会发生反转（即乘以 $-1$）。

小可一心想让最终获得的能量总和最大，他可以不拾取任何石头（此时总和为 $0$）。请你帮他计算出这个最大总和值。

输入格式

第一行一个整数 $n$，表示魔法石的数量。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每颗魔法石的能量值。

输出格式

一个整数，表示能获得的最大能量总和。

样例

5
-1 2 -3 4 -5

14

样例解释

小可可以拾取第 $2, 3, 4, 5$ 颗石头，拾取顺序及能量变化为：

• 第 $1$ 次拾取 $2$（保持） → $+2$
• 第 $2$ 次拾取 $-3$（反转） → $+3$
• 第 $3$ 次拾取 $4$（保持） → $+4$
• 第 $4$ 次拾取 $-5$（反转） → $+5$ 总和为 $2 + 3 + 4 + 5 = 14$。

数据范围

对于 $30\%$ 的数据，$1\le n\le 20$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$-10^4 \le a_i \le 10^4$。