#942 Pepero Disposal

Statement

Statement language

There are $N$ people in a line. The $i$ -th person from the left initially has $A_i$ sticks of Pepero and faces left or right. There is a trash can to the left of person $1$ and another to the right of person $N$ .

You may repeat the following operation.

Choose a person who has at least one stick.
That person passes one stick to the adjacent person in the direction they face. If there is no adjacent person in that direction, the stick is put in the trash can.
That person reverses the direction they face.

A discarded stick cannot be retrieved. You may choose people in any order. Find the minimum number of operations needed to discard all sticks.

Input

The input has the following format.

$N$ $A_1\ A_2\ \cdots\ A_N$

Output

Print the minimum number of operations needed to discard all sticks.

Constraints

$1 \leq N \leq 200\ 000$ .
$0 \leq A_i \leq 10^8$ ().

Subtasks

#	Score	Constraints
1	5	$N=1$ .
2	25	$N\leq30$ ; $\sum A_i\leq30$ .

Samples

Sample 1

Input

5
1 2 0 1 0
RLRRL

Output

31

Sample 2

Input

2
1 0
RL

Output

3