408314: GYM103091 N Parity

Alice and Bob are in charge of the front row bleachers during the Big Game. The bleacher consists of $$$N$$$ seats which have numbers written on them. Each seat will only have one integer on it. Multiple seats may have the same number.

Alice and Bob decide that the Stanford students can take any even numbered seat and the Cal students can take an odd numbered seat.

The night before the game, Alice and Bob's supervisor decides that they want to make sure the seats alternate between Berkeley and Stanford students so they can make new friends.

Alice and Bob thus need to change some of the numbers written on the seats! For every seat, they decide they can add some non-negative integer (including 0) so that the resulting row of seats has numbers of alternating parity. The numbers they add need not be distinct. What's the minimum total sum of numbers they need to add?

Note: Parity simply refers to whether a number is odd or even. 2 has even parity, and 3 has odd parity.

The first line of input is a single integer N ($$$1 \leq N \leq 10^{5}$$$) which is the number of seats. The second line is a list of space separated integers $$$a_i$$$ ($$$ 1 \leq a_i \leq 10^3$$$), which each integer represents the number originally written on each seat.

The output should be an integer, representing the minimum total sum of numbers to be added.

7
4 1 34 99 62 5 56

0

4
1 1 3 3

2

Sample 1: The numbers are already alternating parity, so no numbers need to be added.

Sample 2: Alice and Bob can add 1 to either the first and third seats, which results in an array of [2, 1, 4, 3], or they can add 1 to the second and fourth seats which results in an array of [1, 2, 3, 4].