Time Limit : sec, Memory Limit : KB
English / Japanese  

Pancake

At the pancake shop where you work, the pancake batter is cooked on a long, narrow griddle in a single horizontal row. The pancake can be made by flipping it over several times with a spatula. The number of times you have to flip the pancake is different for each pancake.

Since the spatula is large, two neighbor pancakes will be flipped at the same time. In this case, the positions of these two pancakes are not switched. However, only both ends can be flipped over with just one pancake. When all the pancakes have been flipped over the required number of times, they can be removed from the griddle at once.

You don't want to flip the pancakes too many times because they will become hard if you flip them more times than required. So you decided to find a way to minimize the sum of the number of times each pancake must be flipped before it is all done.

Given the number of pancakes on the griddle and the number of times each pancake must be flipped, make a program to find the minimum sum of the number of times each pancake must be flipped over before it is all done (not the number of times the spatula is manipulated.)

Input

The input is given in the following format.

N
p1 p2 ... pN

In the first line, the number of pancakes N (3 ≤ N ≤ 5000) is given. In the second line, the number of times pi (0 ≤ pi ≤ 3) that each pancake must be flipped is given.

Output

Output the minimum sum of the number of times each pancake must be flipped over before it is all done in a line.

Sample Input 1

3
1 2 1

Sample Output 1

4

If you flip the leftmost and middle pancakes by manipulating the spatula once, the two pancakes will be flipped once each, so the number of times they will be flipped is 2. Also, if you flip the middle and rightmost pancakes by manipulating the spatula once, the two pancakes will be flipped once each, so the number of times they will be flipped is 2. The sum of the above is 4.


Sample Input 2

3
0 3 0

Sample Output 2

6

If you flip the leftmost and middle pancakes by manipulating the spatula once, the number of times they will be flipped is 2. When this is repeated three times, the total number of times the pancakes will be flipped is 6 (note that the middle pancake can only be flipped together with one of its neighbors.)