Little H is an architect who has received a task: to build a row of buildings according to a blueprint. The blueprint provides $n$ non-negative integers from left to right. For the $i$-th number $h_i$, it indicates that the height of the building constructed at position $i$ must not be less than $h_i$.

Little H's method of building is quite special. At any moment, he can always increase the heights of two adjacent buildings by 1 unit and 2 units, respectively. Specifically, for any $i$ ($1 \le i < n$), at each moment, he can choose one of the following two construction methods:

1. Increase the height of the building at position $i$ by 2, and increase the height of the building at position $i+1$ by 1.
2. Increase the height of the building at position $i$ by 1, and increase the height of the building at position $i+1$ by 2.

Little H wants to know the minimum time required to build this row of buildings such that they satisfy the requirements of the blueprint.

Input

The first line contains an integer $n$. The second line contains $n$ integers, $h_1, h_2, \dots, h_n$.

Output

A single line containing the answer, representing the minimum time required.

Examples

Input 1

4
2 1 1 2

Output 1

2

Note 1

Initially, the heights of the four buildings are 0 0 0 0. Little H needs at least the following two construction steps: 1. Increase the heights at positions 1 and 2 by 2 and 1, respectively; the heights become 2 1 0 0. 2. Increase the heights at positions 3 and 4 by 1 and 2, respectively; the heights become 2 1 1 2.

Input 2

13
12 13 9 8 3 21 7 10 1 1 8 1 1

Output 2

35

Subtasks

Let $h_{max} = \max\{h_1, h_2, \dots, h_n\}$.