D. Max Absolute Sum

Given an array ~A~ of ~n~ elements ~[a_1, a_2, \dots, a_n]~, you can choose any subsequence of elements from ~A~ and compute its absolute sum. What is the maximum absolute sum you can obtain?

Input

• The first line contains a single integer ~n~ (~1 \le n \le 10^3~) - the number of elements in the array ~A~.
• The second line of each test case contains ~n~ integers ~a_1, a_2, ..., a_n~ (~-10^6 \le a_i \le 10^6~) - the elements of the array.

Output

• Output a single integer - the maximum sum you can obtain.

Samples

5
1 -2 3 -4 5

9

11
-1 -1 -1 -1 -1 -1 1 1 1 1 1

Sample Output 2

6

Notes

In first example, you can choose subsequence ~[a_1, a_3, a_5]~, and obtain ~|a_1 + a_3 + a_5| = |1 + 3 + 5| = 9~ is maximum absolute sum.