CF1491G Switch and Flip

There are $ n $ coins labeled from $ 1 $ to $ n $ . Initially, coin $ c_i $ is on position $ i $ and is facing upwards (( $ c_1, c_2, \dots, c_n) $ is a permutation of numbers from $ 1 $ to $ n $ ). You can do some operations on these coins. In one operation, you can do the following: - Choose $ 2 $ distinct indices $ i $ and $ j $ . - Then, swap the coins on positions $ i $ and $ j $ . - Then, flip both coins on positions $ i $ and $ j $ . (If they are initially faced up, they will be faced down after the operation and vice versa) Construct a sequence of at most $ n+1 $ operations such that after performing all these operations the coin $ i $ will be on position $ i $ at the end, facing up. Note that you do not need to minimize the number of operations.

N/A

N/A

Let coin $ i $ facing upwards be denoted as $ i $ and coin $ i $ facing downwards be denoted as $ -i $ . The series of moves performed in the first sample changes the coins as such: - $ [~~~2,~~~1,~~~3] $ - $ [-3,~~~1,-2] $ - $ [-3,~~~2,-1] $ - $ [~~~1,~~~2,~~~3] $ In the second sample, the coins are already in their correct positions so there is no need to swap.