D. Beautiful Roses
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Olya has a garden with $$$n$$$ roses. All roses are arranged in a row and numbered from $$$1$$$ to $$$n$$$. The height of the $$$i$$$-th rose is $$$a_i$$$ centimeters.

Olya wants each rose to look beautiful. She believes that a rose looks beautiful if the heights of its neighbors have the same parity; the edge roses are always considered beautiful.

To make the garden beautiful, Olya has a magic fertilizer that instantly increases the height of any rose by $$$1$$$ centimeter. Olya does not want to spend a lot of fertilizer, so she needs to know the minimum number of times she needs to apply the fertilizer to make all the roses in the garden beautiful.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 100000)$$$ — the number of roses in the garden.

The second line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — the heights of all roses in the order of their numbers.

Output

Output a single integer — the minimum number of times the fertilizer needs to be applied to make all the roses look beautiful.

Examples
Input
3
5 4 5
Output
0
Input
3
5 5 5
Output
0
Input
7
3 12 4 6 2 3 3
Output
3
Note

There is only one way to change the garden — apply the magic fertilizer to the roses.