Mika elhatározta, hogy átrendezi rendkívül nagy könyvespolcát, de hogy ne nagyon fáradjon el, úgy döntött, pontosan két könyvet fog egymással felcserélni. Minden könyve egy számjeggyel van megjelölve. Mika a könyvek sorrendjének a szépségét úgy definiálja, hogy az a könyvekhez hozzárendelt számjegyekből kapott szám, ha azokat sorban olvassuk. Segítsetek Mikának, hogy úgy válassza ki a két felcserélendő könyvet, hogy a sorrend szépsége minél nagyobb legyen!

Bemenet

A szabványos bemenet első sorában az \(N\) szám található, vagyis a polcon elhelyezkedő könyvek száma. A második sorban \(N\) számjegy van: \(A_1, A_2, \dots, A_N\), ahol \(A_i\) az \(i\)-edik könyvre írt számjegy.

Kimenet

A szabványos kimenet első és egyetlen sorában kiíratni az \(N\) számjegyet szóközökkel elválasztva, már olyan sorrendben, ahogy azt két könyv olyan célú felcserélésével kapjuk, hogy a kapott sorrend szépsége a lehető legnagyobb legyen.

1. példa

Bemenet

3
8 2 5

Kimenet

8 5 2

2. példa

Bemenet

2
6 3

Kimenet

3 6

Korlátozások

• Minden \(i\)-re érvényes, hogy \(0 \leq A_i \leq 9\).
• \(A_1 \neq 0\).
• Legalább két könyv jelzése nem 0.

A tesztpéldák öt független csoportba oszthatók:

• Tesztpéldák, melyek \(10\) pontot érnek, \(N = 2\).
• Tesztpéldák, melyek \(30\) pontot érnek, \(N \leq 8\).
• Tesztpéldák, melyek \(20\) pontot érnek, a kezdeti sorrend szépsége a polcon legfeljebb \(4 \cdot 10^{18}\).
• Tesztpéldák, melyek \(20\) pontot érnek, \(N \leq 1000\).
• Tesztpéldák, melyek \(20\) pontot érnek, \(N \leq 10^6\).