题目内容

小塔在研究一个有趣的数组翻转操作问题，其中为了考虑均衡，他会同时翻转相邻两个数。他有一个长度为$N$的数组$a[]$，并可以进行任意次操作:选择相邻的两个数，翻转这两个数的符号，即将$a[i]$和$a[i+1](0≤i<n-1)$的符号都翻转。符号翻转的意思是正数变负数，负数变正数，在程序中即让$num=-num$，也即数学中的取相反数;当然$0$翻转后还是$0$。小明的任务是找到经过任意次数(可以为$0$次)这些操作后，能够获得的最大数组和。当然，只要小明觉得有必要，同一个数也可以被反复选择。

输入描述

第一行包含一个整数$N$，表示数组的长度。

第二行包含$N$个整数，$a[1],a[2],..a[N]$。

$1≤N≤30000$，$-1000000000≤a[i]≤1000000000$。

输出描述

输出一个整数，表示经过任意次操作后数组的最大和

样例1

输入

5
1 -2 3 -4 5

输出

15

说明

在这个样例中，初始数组的和是'$1-2+3-4+5=3$'

通过选择相邻的$-2$和$3$翻转符号成[$1,2,-3,-4,5$]，再选择$-3$和$-4$翻转符号，使得数组变为'[$1，2，3，4，5$]'，得到的和是'$1+2+3+4+5=15$'。