Minimize Sum of Even Indices

You are given an array of n integers. You may reorder the array arbitrarily. Your task is to rearrange the array so that the sum of the indices (0-indexed) of all even numbers is minimized.

Let the number of even numbers be \( k \). In the optimal arrangement, all even numbers will be placed in the first \( k \) positions (i.e. indices \( 0, 1, \ldots, k-1 \)). Thus, the minimum possible sum is

[ S = 0 + 1 + 2 + \dots + (k-1) = \frac{k,(k-1)}{2} ]

If there are no even numbers in the array, the answer is 0.

Input and Output are via standard input and output respectively.

inputFormat

The first line contains an integer \( n \) (the number of elements in the array). The second line contains \( n \) space-separated integers representing the array elements.

outputFormat

Output a single integer: the minimum possible sum of the indices of all even numbers after optimally rearranging the array.

6
3 2 4 1 5 6

3