Processing math: 100%

Home


Contest: Task: Related: TaskC TaskE

Score : 400 points

Problem Statement

There are N integers, A1,A2,...,AN, arranged in a row in this order.

You can perform the following operation on this integer sequence any number of times:

Operation: Choose an integer i satisfying 1iN1. Multiply both Ai and Ai+1 by 1.

Let B1,B2,...,BN be the integer sequence after your operations.

Find the maximum possible value of B1+B2+...+BN.

Constraints

  • All values in input are integers.
  • 2N105
  • 109Ai109

Input

Input is given from Standard Input in the following format:

N
A1 A2 ... AN

Output

Print the maximum possible value of B1+B2+...+BN.


Sample Input 1

3
-10 5 -4

Sample Output 1

19

If we perform the operation as follows:

  • Choose 1 as i, which changes the sequence to 10,5,4.
  • Choose 2 as i, which changes the sequence to 10,5,4.

we have B1=10,B2=5,B3=4. The sum here, B1+B2+B3=10+5+4=19, is the maximum possible result.


Sample Input 2

5
10 -4 -8 -11 3

Sample Output 2

30

Sample Input 3

11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000

Sample Output 3

10000000000

The output may not fit into a 32-bit integer type.

'],['\\(','\\)']], processEscapes: true, skipTags: ['prepp'], processClass: "mathjax", ignoreClass: "no-mathjax" } });