Mars Car Numbers

Mars is introducing a new car number system. In this system, each number plate is a permutation of $N$, that is, a sequence in which each of the numbers $1 \ldots N$ appears exactly once.

For administrative purposes, Mars is divided into a southern and a northern hemisphere. So that a car's number shows which hemisphere it comes from, the southern hemisphere uses the $N!/2$ lexicographically smallest plates, and the northern hemisphere uses the $N!/2$ lexicographically largest plates.

The governors want special numbers. The southern governor takes the lexicographically largest number among the plates of the southern hemisphere, and the northern governor takes the lexicographically smallest number among the plates of the northern hemisphere.

Write a program that finds the numbers the two governors receive.

$N!$ denotes the product $1 \cdot 2 \cdot \ldots \cdot N$. A sequence $a = (a_1, a_2, \ldots, a_n)$ is lexicographically smaller than $b = (b_1, b_2, \ldots, b_n)$ if, for some index $t$, $a_1 = b_1$, $a_2 = b_2$, \ldots, $a_t = b_t$ and $a_{t+1} < b_{t+1}$.

The only line of the text file contains an integer $N$ ($2 \le N \le 5 \cdot 10^5$), the length of the Mars car numbers.

The text file must contain exactly two lines, each with $N$ integers separated by spaces. The first line is the number of the southern governor's car, and the second line is the number of the northern governor's car.