Find the minimum number of moves necessary to reorder an array so that all even numbers are at the front and all odd numbers are at the back.

A single move allows you to swap elements at any two indices in the array. For example, if the array is arr = [17, 4, 8], you can swap arr[0] and arr[2] to get arr = [8, 4, 17] in a single move.

Determine the minimum number of moves required to sort the array such that all even elements are at the beginning of the array and all odd elements are at the end of the array.

Example

arr = [6, 3, 4, 5]

The following four arrays are valid custom-sorted arrays:

• a = [6, 4, 3, 5]
• a = [4, 6, 3, 5]
• a = [4, 5, 3, 6]
• a = [4, 6, 5, 3]

The most efficient sorting requires 1 move: swap the 4 and the 3.

Function Description

Complete the function moves in the editor with the following parameter(s): int arr[n]: an array of positive integers

Returns

int: the minimum number of moves it takes to sort an array of integers with all even elements at earlier indices than any odd element

Note: The order of the elements within even or odd does not matter.

Constraints

• 2 < n < 10^5
• 1 ≤ arr[i] ≤ 10^9, where 0 ≤ i < n.
• It is guaranteed that array a contains at least one even and one odd element.