Problem Description

Ringo is playing one-dimensional Othello. One-dimensional Othello is a game played with an infinitely long row of squares and special pieces. The pieces used in one-dimensional Othello have a black side and a white side. Flipping a black piece results in a white piece, and flipping a white piece results in a black piece. The game proceeds as follows:

1. First, place white pieces $ A_1 $ times, black pieces $ A_2 $ times, white pieces $ A_3 $ times, ..., and white pieces $ A_N $ times in this order consecutively on the squares.
2. Place a black piece on any empty square. This must be adjacent to exactly one square with a white piece.
3. Flip all white pieces between the black piece placed in step 2 and the nearest other black piece (such a piece is always uniquely determined).
4. Perform the operations in steps 2 and 3 with black and white swapped.
5. Repeat steps 2 to 4.
6. If all pieces become the same color at the end of step 3 or 4, the game ends at that point.

Since flipping many pieces is cumbersome, Ringo wants to minimize the number of flips. Find the minimum sum of the number of pieces Ringo flips until the game ends.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ ... $ A_N $

• The first line contains an integer $N\ (3\ ≦\ N\ <\ 10^5,\ N\ is\$.
• The second line contains $ N $ integers representing the initial configuration of the pieces, separated by spaces. The $i\ (1\ ≦\ i\ ≦\ N)$ -th integer is $A_i\ (1\ ≦\ A_i\ ≦\ 10^8)$.

Output Format

Output the minimum sum of the number of pieces Ringo flips until the game ends on one line. End the output with a newline.

Sample Input and Output

Sample Input #1

5
1 2 3 4 5

Sample Output #1

20

Sample Input #2

9
100000000 20 15 11 14 20 15 11 15

Sample Output #2

554

Notes/Hints

Sample Explanation 1

By placing the pieces as shown in the figure below, a total of $1+4+5+10\ =\ 20$ flips are made.

见题面 Input 部分

见题面 Output 部分