Problem Description

Snuke is on a number line. He has $ L $ ears and walks continuously on the number line while satisfying the following conditions:

• He does not pass through points with coordinates less than $ 0 $ or greater than $ L $
• He starts and ends his walk at integer coordinates
• He can only change direction at integer coordinates

Every time Snuke passes through a point represented by the coordinate $ i-0.5 $ using integer $ i $, he puts one stone into the $ i $th ear.

After Snuke finishes his walk, Ringo wants to perform the following operations any number of times in any order to ensure that each $ i $th ear of Snuke contains exactly $ A_i $ stones:

• Choose one of Snuke's ears and put one stone in it
• Choose one of Snuke's ears that contains at least one stone and take one stone out

When Ringo can freely decide the way Snuke walks, find the minimum number of operations needed.

Input Format

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

$ L $ $ A_1 $ $ : $ $ A_L $

Output Format

Output the minimum number of operations needed.

Sample Input and Output

Sample Input #1

4
1
0
2
3

Sample Output #1

1

Sample Input #2

8
2
0
0
2
1
3
4
1

Sample Output #2

3

Sample Input #3

7
314159265
358979323
846264338
327950288
419716939
937510582
0

Sample Output #3

1

Notes/Hints

Constraints

• $1 \leq L \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^9 (1 \leq i \leq L)$
• All inputs are integers

Sample Explanation 1

Suppose Snuke walks as follows: - Starts at coordinate $ 3 $ and ends at coordinate $ 4 $. Visits coordinates $ 3, 4, 3, 2, 3, 4 $ in order. At this point, Snuke's ears contain $ 0, 0, 2, 3 $ stones respectively. Ringo can satisfy the condition by putting one stone into Snuke's first ear.

见题面 Input 部分

见题面 Output 部分