Ordenación por paridad y valor— Tarea de la comunidad

Dado un arreglo de números enteros. Es necesario ordenarlo de tal manera que primero vayan todos los números pares en orden ascendente, y luego todos los números impares en orden descendente. Si un número es igual a 0, se considera par. Implemente la ordenación sin utilizar métodos de ordenación incorporados, usando el algoritmo de ordenación por mezcla (merge sort). Adicionalmente, después de la ordenación, imprima la cantidad de permutaciones realizadas durante la ordenación (es decir, la cantidad de intercambios de elementos).

Formato de entrada

La primera línea contiene un número entero N (1 ≤ N ≤ 1000) — la cantidad de elementos en el arreglo. La segunda línea contiene N números enteros separados por espacios — los elementos del arreglo.

Formato de salida

Imprima el arreglo ordenado en una sola línea separado por espacios. Luego, en la siguiente línea, imprima un número entero — la cantidad de intercambios realizados.

Ejemplos

Ejemplo 1

ENTRADA

4
0 7 2 9

SALIDA

0 2 9 7
2

Ejemplo 2

ENTRADA

6
6 5 4 3 2 1

SALIDA

2 4 6 5 3 1
5