Tri par parité et valeur— Tâche communautaire

Soit un tableau d’entiers. Il faut le trier de sorte que tous les nombres pairs apparaissent en premier dans l’ordre croissant, puis tous les nombres impairs dans l’ordre décroissant. Si un nombre est égal à 0, il est considéré comme pair. Implémentez le tri sans utiliser les méthodes de tri intégrées, en utilisant l’algorithme de tri par fusion (merge sort). En complément, après le tri, affichez le nombre de permutations effectuées lors du tri (c’est-à-dire le nombre d’échanges d’éléments).

Format d\ entrée

La première ligne contient un entier N (1 ≤ N ≤ 1000) — le nombre d’éléments dans le tableau. La deuxième ligne contient N entiers, séparés par des espaces — les éléments du tableau.

Format de sortie

Affichez le tableau trié sur une seule ligne, séparé par des espaces. Ensuite, sur la ligne suivante, affichez un entier — le nombre d’échanges effectués.

Exemples

Exemple 1

ENTRÉE

4
0 7 2 9

SORTIE

0 2 9 7
2

Exemple 2

ENTRÉE

6
6 5 4 3 2 1

SORTIE

2 4 6 5 3 1
5