Things Got Out of Hand

Time limit1sMemory limit1024 MB

Summary

Arrange 1 to N in a permutation so that multiplying at odd positions and adding at even positions gives the largest final value of X, starting from 1.

Level: Medium5 of 10
Topics: Greedy, Implementation
Solved: No attempts yet

Problem

Woojin arranges the integers 1, 2, \cdots, N in any order to make a permutation $p = [p_1, p_2, \cdots, p_N]$ . He then uses this permutation to grow an integer X that he holds. The initial value of X is 1.

For each i from 1 to N, Woojin can grow X using p_i as follows.

If i is odd, multiply X by p_i.
If i is even, add p_i to X.

For example, when N = 4 and p = [1, 2, 3, 4], X changes as $1 \times 1 = 1$ , $1 + 2 = 3$ , $3 \times 3 = 9$ , $9 + 4 = 13$ .

Given N, find how to arrange the integers 1, 2, \cdots, N so that X grows as large as possible.

Input

A single integer $N$ ( $1 \le N \le 100$ ) is given.

Output

Print the permutation $p = [p_1, p_2, \cdots, p_N]$ that makes X as large as possible, with the values separated by spaces. If several permutations maximize X, print any one of them.

Examples1

Example 1
Input
```
2
```
Expected output
```
2 1
```