Before giving you presents, Santa challenges you to a game of cards. You and Santa are both given cards, labelled from to .
Upon receiving the cards, you and Santa may both reorder the cards however you wish. After reordering the cards, you both lay your cards down from left to right. The total festivity of an arrangement of cards is equal to the number of subarrays where the maximum element is equal to the subarray's size. The player whose hand has the highest festivity is declared the winner. If two arrangements have the same festivity, the one that is lexicographically larger is considered to be superior. Given , your job is to output a hand for both you and Santa such that you win by the largest margin. In other words, output the best and worst possible hands for the game.
Definition: An array is lexicographically larger than an array if and at the first index where , .
Constraints
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [70%]
No additional constraints.
Input Specification
The first and only line contains a single integer, .
Output Specification
On the first line, output space-separated integers, the best possible card arrangement for the game.
On the second line, output space-separated integers, the worst possible card arrangement for the game.
Sample Input
3
Sample Output
3 2 1
1 3 2
Explanation of Sample
Here, the largest festivity possible is 3, and the smallest festivity possible is 2. Note that the output matches the lexicographical specifications provided.
Comments