Cerința

Se dau n numere întregi. Să se insereze între oricare două numere de aceeași paritate media lor aritmetică.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere întregi, separate prin spații.

Date de ieșire

Programul va afișa pe ecran elementele noului șir de numere obținut după inserarea elementelor, separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 100
• -1.000.000.000 ≤ elementele șirului ≤ 1.000.000.000

Exemplu:

Intrare

5
1 21 3 4 8

Ieșire

1 11 21 12 3 4 6 8

Explicație

Între 1 și 21 se inserează numărul (1+21)/2=11. Între 21 și 3 se inserează numărul (21+3)/2=12. Între 3 și 4 nu se inserează nimic, pentru că au paritate diferită. Între 4 și 8 se inserează numărul 6.