eolymp
bolt
Try our new interface for solving problems
Problems

About Frogs

About Frogs

Once \textbf{N} white and \textbf{N} black frogs decided to play a game. They found \textbf{2N+1} tussocks and numbered them from \textbf{0} to \textbf{2N}. Then the frogs occupied the tussocks in such a way that the white frogs sit on the tussocks with numbers \textbf{0}...\textbf{N--1}, the black frogs sit on the tussocks with numbers \textbf{N+1}...\textbf{2N}, and the tussock \textbf{N} is empty. The goal is to swap the white and black frogs, i.e., in the end of the game the first \textbf{N} tussocks must be occupied by the black frogs, and the last \textbf{N} tussocks must be occupied by the white frogs. In this game, the following moves are allowed. Frogs may jump only to empty tussocks. A black frog may jump from a tussock numbered \textbf{i} > \textbf{0} to the tussock \textbf{i--1}, or it may jump from a tussock \textbf{j} > \textbf{1} to the tussock \textbf{j--2} if there is a white frog on the tussock \textbf{j--1}. Similarly, a white frog may jump from a tussock \textbf{i} < \textbf{2N} to the tussock \textbf{i+1}, or it may jump from a tussock \textbf{j} < \textbf{2N-1} to the tussock \textbf{j+2} if there is a black frog on the tussock \textbf{j+1}. Usually in games white and black make moves by turns, but here white and black frogs have the same goal, so they may make moves in any order, and the total number of moves of white frogs may differ from the total number of moves of black frogs. If after one million moves the frogs still have not swapped, they become bored of the game and jump into the water. Given \textbf{N}, determine if the frogs can achieve their goal. \InputFile The input is a single integer \textbf{N} in the range from \textbf{1} to \textbf{499}. \OutputFile If the frogs cannot swap, then output the number \textbf{--1}. Otherwise, in the first line output the number of moves \textbf{K} needed for the fulfillment of the task, and in the second line output the sequence of numbers \textbf{С_i} separated by a space (\textbf{1} ≤ \textbf{i} ≤ \textbf{K}), where \textbf{С_i} is the number of the tussock from which a jump is performed at the \textbf{i}^th move. If there are many solutions, you may output any of them.
Time limit 1 second
Memory limit 64 MiB
Input example #1
1
Output example #1
3
2 0 1 
Author Alexander Ipatov
Source Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006