Autonumbrid

Marslased juurutavad uut autonumbrite süsteemi. Selles süsteemis on iga numbrimärk $N$ arvu permutatsioon, see tähendab jada, milles arvud $1 \ldots N$ esinevad igaüks täpselt ühe korra.

Administratiivselt jaguneb Marss lõuna- ja põhjapoolkeraks. Kuna on soovitav, et auto numbri järgi saaks tuvastada, kummalt poolkeralt see pärineb, otsustati, et lõunapoolkera saab $N!/2$ leksikograafiliselt väiksemat ja põhjapoolkera $N!/2$ leksikograafiliselt suuremat numbrit.

Poolkerade kubernerid tahtsid endale erilisi numbreid. Lõunapoolkera kuberner otsustas võtta endale oma poolkera numbritest leksikograafiliselt suurima ja põhjapoolkera kuberner oma poolkera numbritest leksikograafiliselt vähima.

Kirjuta programm, mis leiab, millised numbrid kubernerid endale saavad.

Meenutame, et $N!$ tähistab korrutist $1 \cdot 2 \cdot \ldots \cdot N$ ning arvujada $a = (a_1, a_2, \ldots, a_n)$ on arvujadast $b = (b_1, b_2, \ldots, b_n)$ leksikograafiliselt väiksem, kui mingi indeksi $t$ korral $a_1 = b_1$, $a_2 = b_2$, \ldots, $a_t = b_t$, aga $a_{t+1} < b_{t+1}$.

Tekstifaili ainsal real on täisarv $N$ ($2 \le N \le 5 \cdot 10^5$) --- Marsi autonumbrite pikkus.

Tekstifaili väljastada täpselt kaks rida, kummalegi reale $N$ tühikutega eraldatud täisarvu. Esimesele reale väljastada lõunapoolkera ja teisele põhjapoolkera kuberneri auto number.