Mihai Eminescu și George Coșbuc merg printr-un parc

Printre schițele lui Mihai Eminescu a fost găsită această problemă (jk am facut-o noi)

Cerință

Se dă $n$ și un șir $a$ de numere naturale. Definim o operație astfel:

Se aleg două poziții $i$ și $j$. Se interschimbă cifrele de pe pozițiile pare ale lui $a_i$ și $a_j$. Care este numărul maxim și minim care se poate obține în șir, după un anumit număr de operații?

De exemplu, pentru numărul $14 \ 563$:

• cifra $3$ se află pe poziția $1$
• cifra $6$ se află pe poziția $2$
• cifra $5$ se află pe poziția $3$
• cifra $4$ se află pe poziția $4$
• cifra $1$ se află pe poziția $5$

Date de intrare

Pe prima linie se găsește un număr întreg $n$. Pe următoarea linie se vor găsi $n$ numere întregi, reprezentând șirul $a$.

Date de ieșire

Pe prima linie se vor găsi două numere întregi, numărul maxim, respectiv minim care se poate obține după oricâte operații.

Restricții și precizări

• $2 \leq n \leq 100 \ 000$;
• $10 \leq a_i < 1 \ 000 \ 000 \ 000$, pentru $i$ de la $1$ la $n$;
• Pentru $4$ puncte, $n=2$
• Pentru $4$ puncte, $n=3$
• Pentru $5$ puncte, $n=4$
• Pentru $40$ de puncte, $n \leq 5 \ 000$;
• Atenție! Toate numerele din șir au același număr de cifre.
• Atenție! Numărul maxim și numărul minim nu trebuie să fie obținute după aceleași operații. De exemplu, putem obține mai întâi numărul maxim după câteva operații, iar după alte câteva operații modificăm acest număr maxim și obținem un număr minim.

Exemplul 1

stdin

5
1938 1929 9575 3938 7261

stdout

9979 1221

Explicație

Putem face operația pe $1 \ 929$ și $7 \ 261$, după vor fi egale cu $7 \ 969$ și $1 \ 221$, apoi putem face operația pe $7 \ 969$ și $9 \ 575$, devenind $9 \ 979$ și $7 \ 565$. Se poate demonstra că $1 \ 221$ este numărul cel mai mic care se poate obține, respectiv $9 \ 979$ numărul maxim care se poate obține.

Exemplul 2

stdin

2
644 312

stdout

644 312

Explicație

Putem lăsa numerele așa cum sunt.

Exemplul 3

stdin

4
140 200 665 923

stdout

963 100

Explicație

Mi-e lene, fă singur. 😊