409188: GYM103451 H Krosh and permutation

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Krosh and permutationtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

ExampleInput
2
Output
1
2 1 

加入题单

上一题 下一题 算法标签: