B. Line of Swiftiestime limit per test: 1 secondmemory limit…
B. Line of Swiftiestime limit per test: 1 secondmemory limit per test: 256 megabytes The Society of Consumer Protection (SCP) is receiving lots of complaints. Swifties want to buy merchandise in the concert stand, but the lines are huge. To solve this problem, SCP implemented a queue management system. A group of n Swifties each receive a queue number from 1 to n, and they should only go and buy their stuff once their number is called. This way, they can sit and listen to their favorite singer while it is not their turn to go to the stand. However, Swifties are very superstitious. For instance, they only buy concert tickets from Discord channels, otherwise they will have eternal bad luck. In the scenario above, they will not go to the stand and buy stuff if the number called immediately before them is one less or one more than their queue numbers. A Swiftie with queue number 3 will only go to the stand if the previous called number is not 2 nor 4. The stand owner wants to maximize the number of Swifties that will go to the stand so that the profits are maximized. Can you compute what is the maximum number of Swifties and provide a calling order that will achieve it? Input The input contains a single integer n (1≤n≤5000) — the number of Swifties in the line. Output In the first line print one integer k — the maximum number of Swifties that will go to the stand and buy merchandise. In the second line print k distinct integers a1, a2, …, ak (1≤ai≤n), where ai is a queue number. Remember that |ai - ai+1| ≠ 1 for all i from 1 to k-1. If there are several possible answers, output any of them. Examples Input #1 Output #1 6 61 5 3 6 2 4 Input #2 Output #2 3 21 3
Read Details