There is an array of N integers, you are given a task to make any number of partitions in the array such that the Special Sum of all the partitions combined is maximized.

Suppose you make K partitions then the Special Sum is defined as P₁ - P₂ + P₃ - P₄ + P₅ ..... +(-1)^{(K - 1)}P_k.

Here P_i is defined as summation of all integers in that partition.

Input :

•   The first line of input consist of an integer N, which denotes the number of integers in the array.    
•   The second line of input consist of N integers, which denotes the values of the array.

Output :

•  A single integer which denotes the maximum value of the Special Sum that can be obtained by any number of partitions.

Constraint :

• $1 \leq N \leq 100000$
• $-10^9 \leq values\ inside\ array\leq 10^9$