Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EI2122Q1ADAF1 - The maximum point

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  N ≤ 105).

-      The next line contains N integers which are values of N cells, respectively.

-      All integers don’t exceed 109.

Output

The maximum point.

Sample

Input

Output

5

4 3 -5 6 8

28

 

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


Added by:Ha Minh Ngoc
Date:2021-12-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.