题目描述

薯条哥在研究一个有趣的数组翻转操作问题，其中为了考虑均衡，他会同时翻转相邻两个数。他有一个长度为$n$的数组$a$，并可以进行任意次操作:选择相邻的两个数，翻转这两个数的符号，即将$a_i$和$a_{i+1}(0\le i\le n-1)$的符号都翻转。符号翻转的意思是正数变负数，负数变正数，

在程序中即让$num=-num$，也即数学中的取相反数;当然$0$翻转后还是$0$。薯条哥的任务是找到经过任意次数(可以为$0$次)这些操作后，能够获得的最大数组和。当然，只要薯条哥觉得有必要，同一个数也可以被反复选择。

输入描述

第一行包含一个整数$n(1\le n\le 3\times 10^4)$，表示数组的长度。

第二行包含$n$个整数，$a_1,a_2,..a_n(-10^9\le a_i\le 10^9)$。

输出描述

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

样例

输入

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$。