Cerința

Se dau n numere întregi. Să se insereze între oricare două numere de aceeași paritate media lor aritmetică. Algoritmul se va relua în mod repetat până când nu se mai poate adăuga șirului niciun nou element.

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 pe câte o linie nouă, începând cu șirul inițial, toate șirurile distincte ce se pot construi prin metoda mai sus menționată. Fiecare șir se va scrie pe câte un rând nou.

Restricții și precizări

• în cazul în care șirul conține două elemente consecutive egale, între acestea nu se va insera media aritmetică
• 1 ≤ n ≤ 100
• -1.000.000.000 ≤ elementele șirului ≤ 1.000.000.000

Exemplu:

Intrare

6
1 41 3 3 4 8

Ieșire

1 41 3 3 4 8
1 21 41 22 3 3 4 6 8
1 11 21 31 41 22 3 3 4 5 6 7 8
1 6 11 16 21 26 31 36 41 22 3 3 4 5 6 7 8

Explicație

Primul șir este șirul inițial, din primul șir se obține următorul, de pe linia a doua, apoi șirul al treilea și în final șirul al patrulea. În al patrulea șir nu mai putem insera niciun element nou.