Ordenação por Paridade e Valor— Tarefa da Comunidade

Dado um array de números inteiros. É necessário ordená-lo de forma que primeiro venham todos os números pares em ordem crescente e, em seguida, todos os números ímpares em ordem decrescente. Se o número for 0, ele é considerado par. Implemente a ordenação sem usar métodos de ordenação embutidos, utilizando o algoritmo de ordenação por mesclagem (merge sort). Adicionalmente, após a ordenação, exiba o número de trocas realizadas durante a ordenação (ou seja, a quantidade de trocas de elementos).

Formato de Entrada

A primeira linha contém um número inteiro N (1 ≤ N ≤ 1000) — a quantidade de elementos no array. A segunda linha contém N números inteiros separados por espaços — os elementos do array.

Formato de Saída

Exiba o array ordenado em uma única linha, separado por espaços. Em seguida, na próxima linha, exiba um número inteiro — a quantidade de trocas realizadas.

Exemplos

Exemplo 1

ENTRADA

4
0 7 2 9

SAÍDA

0 2 9 7
2

Exemplo 2

ENTRADA

6
6 5 4 3 2 1

SAÍDA

2 4 6 5 3 1
5