Autonumbrid

시간 제한1초메모리 제한1024 MB

요약

1부터 N까지의 순열을 사전순으로 나열했을 때, 작은 절반 중 가장 큰 순열과 큰 절반 중 가장 작은 순열을 구한다.

난이도: 보통10점 중 5점
유형: 조합론, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 1
입력
```
2
```
예상 출력
```
1 2
2 1
```
예제 2
입력
```
3
```
예상 출력
```
2 1 3
2 3 1
```