20. Чётность соседей

В последовательности целых чисел $A$ требуется переставить минимальное число элементов так, чтобы никакие два соседних числа не были одной чётности.

В первой строке входных данных записано целое число $n$ (1 $\le n \le$ 100,000) — количество элементов в последовательности.

Во второй строке записаны $n$ целых чисел $a_i$ (0 $\le a_i \le$ 1,000,000,000) — элементы последовательности.

В первой строке выведите число $k$ (0 $\le k \le n$) — количество элементов последовательности, которые были переставлены.

Во второй строке выведите $n$ чисел $b_i$. Все числа последовательности $A$ должны быть выведены. Любые два соседних элемента последовательности должны быть различной чётности. Ровно $k$ индексов последовательности $B$ должны отличаться от последовательности $A$. Если подходящих последовательностей $B$ несколько, то выведите любую из них.

Если переставить элементы последовательности с требуемым условием невозможно, то выведите одно число -1.