#932 Some Tanks Are in Siege Mode, Others Go Boom Boom Boom Boom Boom Boom!

Statement

Statement language

You command a powerful unit of siege tanks. Your troops have encountered the enemy and are preparing to attack. The enemy formation occupies positions numbered from $1$ to $N$ in a line. The initial health at position $i$ is $a_i$ . A position with health $0$ contains no enemy.

For each attack, a tank can use either of the following modes.

Siege mode: Choose a position $i$ with $1\le i\le N$ . Decrease the health at position $i$ by $2$ , and the health at each of positions $i-1$ and by . Ignore damage to positions outside the line. This costs .

Health cannot become negative. Decreasing health $h$ by $d$ changes it to $\max(0,h-d)$ . You may attack a position whose health is already $0$ .

Find the minimum total cost required to make the health at every position equal to $0$ .

Input

The input is given in the following format.

$N$ $a_1\ a_2\ \cdots\ a_N$

Output

Print the minimum total cost required to make the health at every position equal to $0$ .

Constraints

$1\le N\le 200\,000$ .
$0\le a_i\le100$ ().

Subtasks

#	Score	Constraints
1	15	$N\le8$ , $a_i\le4$ ( $1\le i\le N$ )

Samples

Sample 1

Input

3
1 2 1

Output

3

In the first example, attack position $2$ once in siege mode.

Sample 2

Input

4
1 2 4 2

Output

7

In the second example, attack position $3$ twice in siege mode, then attack position $1$ once in tank mode. The total cost is $3+3+1=7$ .