There are N robots in a single row each having an integer value assigned to them.Each robot can terminate the closest robot (either left or right) if there is any When a robot with a value x terminates another robot with value y, then terminated robot vanishes and the value of the robot which terminated changes to x-y. The robots will destroy each other until one remains Find the maximum possible value of the last robot.

First line contains integer N and the next line contains N integers where ith element denotes the value of ith robot and these values are given in the same order in which those robots appear in the row.

CONSTRAINTS: 1<N<500000

-10^9 <= A, < 10^9 where A, is the value of ith robot

Example:

Input: 4

2 1 2 1

Output:

4

Explanation:

Second robot terminates third making array 2,-1,1 then second terminates the third one in this new array making the new array as 2,-2 and finally first terminate second leaving with value 4

I thought of doing range dp but it will be O(n^3),and also in the i had a doubt whether to find maximum value or minimum value Any ideas ??