Minimum Swaps for Even / Odd Partition

Requirements

• The first input line provides inputSize, which specifies the array length.
• The second line supplies inputSize integers separated by spaces as inputArr.
• A single move can exchange the values stored at any pair of positions.
• Determine the fewest exchanges needed to place every even value first and every odd value afterward.
• Values within the even portion and within the odd portion may appear in any order.
• Displayed limits are: 2 <= inputSize <= 10^5, 1 <= inputArr[i] <= 10^9.
• The input array is guaranteed to include at least one even number and at least one odd number.

Examples

Input:

4
8 7 2 9

Output:

1

Explanation: exchanging 7 with 2 produces a valid arrangement; for example, [8,2,7,9] and [2,8,9,7] both satisfy the required split.

inputSize = 4
inputArr = 8 7 2 9

1