Se dă un vector cu n elemente numere întregi nenule.

Cerinţa

Să se ordoneze crescător subșirul format din elementele negative din vector și descrescător subșirul format din elementele pozitive. Indicii subșirului format din elementele negative nu se vor schimba. La fel și indicii subșirului format din elementele pozitive.

Date de intrare

Fişierul de intrare halfsortqs.in conţine pe prima linie numărul n si pe a doua linie n numere întregi nenule separate prin spaţii.

Date de ieşire

Fişierul de ieşire halfsortqs.out va conţine pe prima linie cele n elemente ale vectorului, ordonate conform cerinței, separate prin câte un spațiu.

Restricţii şi precizări

• 0 < n ≤ 100.000
• valoarea absolută a numerelor de pe a doua linie a fişierului de intrare va fi mai mică decât 230

Exemplu:

halfsortqs.in

6
2 -1 9 -4 5 7

halfsortqs.out

9 -4 7 -1 5 2  

Explicatie:

Elementele pozitive 2, 9, 5 și 7 se ordonează descrescător și rămân pe pozițiile 1, 3, 5 și 6 (dacă îndexăm de la 1), iar cele negative -1 și -4 se se ordonează crescător și rămân pe pozițiile 2 și 4.