Sorting by parity and value

Java Medium sorting

Task «Sorting by parity and value»

Given an array of integers. It is necessary to sort it so that all even numbers come first in ascending order, followed by all odd numbers in descending order. If a number is 0, it is considered even. Implement sorting without using built-in sorting methods, using the merge sort algorithm. Additionally, after sorting, output the number of swaps performed during sorting (i.e., the number of element exchanges).

Input Format

The first line contains an integer N (1 ≤ N ≤ 1000) — the number of elements in the array. The second line contains N integers separated by spaces — the elements of the array.

Output Format

Output the sorted array in one line, separated by spaces. Then, on the next line, output a single integer — the number of swaps performed.

Examples

Example 1

INPUT

4
0 7 2 9

OUTPUT

0 2 9 7
2

Example 2

INPUT

6
6 5 4 3 2 1

OUTPUT

2 4 6 5 3 1
5

main.java