When Li'angelo ball meets 68

Program time limit: 1 second

Program memory limit: 512 MB

what does 68 and Liangelo Ball have in common? They both have an older brother and a younger brother stealing all the spotlight.

To fix this once and for all, Liangelo Ball travels to the ball-shaped planet lavar, which is populated entirely by lavars.

You can line the lavars up by birth time, so they form an array. The $i$th lavar starts with $a_i$ legs.

Liangelo does not want any lavar to feel like the ignored middle child. So after he is done changing leg counts, no lavar is allowed to have strictly fewer legs than every adjacent lavar.

In plain language:

a middle lavar cannot have fewer legs than both lavars next to it;

Liangelo can add or remove legs. Adding one leg takes one day, and removing one leg also takes one day.

There is one more lavar rule: lavars at odd positions want an odd number of legs, and lavars at even positions want an even number of legs. So position 1 must end odd, position 2 must end even, position 3 must end odd, and so on.

Find the minimum total number of days needed to change the original array $a$ into some final array $b$ satisfying all of the rules above.

Input

The first line contains one integer $N$, the number of lavars. The next $N$ integers are $a_i$, where $a_i$ is the initial number of legs of the $i$th lavar.

Constraints

For all test cases:

$1 \leq N \leq 10^6$.
$0 \leq a_i \leq 10^9$ for all $i$.

Additionally:

For Subtask 1 (30% of points): $1 \leq N \leq 10^3$.
For Subtask 2 (70% of points): there are no additional constraints.

Output

Output the minimum possible total number of days.

Equivalently, output the minimum possible value of

$$ \sum_{i=1}^{N} |a_i - b_i|, $$

where $b$ satisfies the parity rules and the "no ignored middle-child lavar" rule above.

You should write to standard output.

Sample Input 1

3
3 1 3

Sample Output 1

Explanation 1

Increase the middle element by 3.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

Explanation 2

Increase the second and forth element to 2, and the middle element to 3.

Sample Input 3

5
1 2 1 2 1

Sample Output 3

Explanation 3

If you increase the middle element by 2, the array is legal.

Scoring

For each subtask (worth 30% and 70% of points, as per the Constraints section), your program will be run on multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves that subtask. Your program will receive the points for each subtask it solves. Recall that your final score on the task is the score of your highest scoring submission.

Submit unofficially

The contest ended at 8:45 p.m. AEST on Tuesday 7th April. All submissions will be unofficial officially.