Dându-se un vector cu $n$ elemente numere întregi, $a$, să se efectueze modificările necesare, astfel încat vectorul final să aibă elementele inițiale de pe pozițiile impare sortate în ordine crescătoare, iar cele de pe pozițiile pare sortate în ordine descrescătoare.

Cerință

Programul este scris deja, dar conține câteva buguri. Sarcina voastră este să îl reparați. Programul se poate găsi aici sau în secțiunea „Atașamente” din lateral.

Date de intrare

Se va citi din terminal de pe prima linie un număr natural $n$ ($n \leq 1\ 000$), urmat pe a doua linie de un vector $a$, de $n$ elemente, numere întregi, separate prin câte un spațiu. Orice număr poate fi stocat într-un int.

Date de ieșire

Se va afișa pe o linie vectorul modificat $a$, cu elementele sortate în ordinea cerută. Elementele afișate vor fi separate prin câte un spațiu.

Note

1. Antetul funcțiilor de sortare și pasul contorului din cadrul acestora nu poate fi modificat.
2. Conținutul instrucțiunii repetitive do while() din cadrul funcției main() nu poate fi modificat.
3. Nu se pot adăuga linii de cod în program, însă se pot șterge sau modifica liniile de cod existente (cu excepția celor de la restricțiile 1 și 2).
4. Fun fact: Puteți rezolva cum vreți problema. Nicio regulă din cele menționate anterior nu este verificată, dar în timpul concursului probabil că erau verificate.

Exemplul 1

stdin

5
6 2 3 5 10

stdout

3 5 6 2 10

Exemplul 2

stdin

6
10 7 3 2 5 6

stdout

3 7 5 6 10 2