H. Krosh and permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Krosh is going to celebrate his birthday soon. He thinks that friends will present him some permutation $$$p$$$ of $$$n$$$ numbers from $$$1$$$ to $$$n$$$. Krosh may dislike permutation because he likes fixed points. These are such positions $$$i$$$ where $$$p_i = i$$$. He wants permutation to contatin at least one fixed point. So he can do following moves with the presented permutation: swap any two adjacent elements in it. Krosh knows how to make minimum number of moves to obtain his goal but there is a new question for him: what is the maximum number of such moves he can do in worst scenario?

Input

You are given $$$1 \le n \le 10^5$$$ – size of permutation.

Output

In first line output maximum number of moves Krosh can make in worst case. In second line output the permutation on which this number of moves is obtained. If there are more than one answer output any of them.

Example
Input
2
Output
1
2 1