Given a row of ~N~ cells, numbered from ~1~ to ~N~. Each cell contain a given value. If a cell containing the value of ~V~ is selected, you will earn ~V~ points, otherwise, you will earn ~2*V~ points. Note that for every two adjacent cells, you must select at least one of them. Calculate the maximum point you can earn.

Input

• The first line contains one integer ~N~ - the number of cells (~1 \leq N \leq 10^5~).
• The next line contains ~N~ integers which are values of ~N~ cells, respectively.
• All integers don't exceed ~10^9~.

Output

• The maximum point.

Example Input 1

5
4 3 -5 6 8

Example Output 1

28

• Hints: Max Points = ~2*4 + 3 - 5 + 6 + 2*8 = 28~. See problems Logging ~1\&2\&3~