Treasure Hunt Dig Game

You are playing a treasure-hunting game on a linear board of n cells numbered from 1 to n. In each cell i, every layer you dig yields a value of p_i. However, your digging is subject to the following constraints:

• The difference in digging depth between any two adjacent cells must not exceed 1, i.e. for all 1 ≤ i < n,
  \( |d_{i+1} - d_i| \le 1 \).
• The first and the last cell can have at most 1 layer dug, i.e.
  \( d_1 \le 1 \) and \( d_n \le 1 \).

Your task is to choose an integer digging depth d_i (≥ 0) for each cell so as to maximize the total obtained value:

[ \text{Total Value} = \sum_{i=1}^{n} p_i \cdot d_i, ]

subject to the constraints described above.

Input Constraints: The number of cells n is given, followed by n integers p₁, p₂, \dots, p_n.

inputFormat

The first line contains a single integer n (the number of cells). The second line contains n space-separated integers, where the i-th integer p_i denotes the value gained for each layer dug at cell i.

outputFormat

Output a single integer, representing the maximum total value you can obtain under the given constraints.

sample

3
1 2 3

8