CF2246F Whoname and Unsorted Array

Given a permutation $ ^{\text{∗}} $ $ p $ of length $ n $ , you may perform the following operation on it any number of times (possibly zero): - Choose an index $ i $ where $ 1 \leq i \leq n-1 $ , and move $ p_i $ to $ p_1 $ (shifting everything in between to the right) and $ p_{i+1} $ to $ p_n $ (shifting everything in between to the left). Formally, you may transform $ p = [p_1, \ldots, p_n] $ into $ p' = [p_i, p_1, p_2, \ldots, p_{i-1}, p_{i+2}, p_{i+3}, \ldots, p_n, p_{i+1}]. $ Provide a valid sequence of operations of length at most $ 4n $ to make $ p_i = i $ for all $ i\,(1 \le i \le n) $ , or print $ -1 $ if no sequence exists. It can be shown that if a valid sequence of operations exists, there is a valid sequence of length at most $ 4n $ operations. $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The description of the test cases follows. The first line contains an integer $ n\,(2 \leq n \leq 5000) $ — the length of the permutation. The second line contains $ n $ integers $ p_1, p_2, \ldots, p_n \, (1 \le p_i \le n) $ . It is guaranteed that $ p $ is a permutation. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5000 $ .

If there does not exist a valid sequence of operations, output $ -1 $ . Otherwise, on the first line, output $ x\,(0 \leq x \leq 4n) $ , the number of operations needed to sort the permutation. On the second line, output $ x $ integers $ i_1, \ldots, i_x $ where $ i_j $ ( $ 1 \leq i_j \leq n-1 $ ) denotes the index corresponding to the $ j $ -th operation.

For the first example, it can be shown that no sequence of operations can sort the permutation. For the second example, one valid sequence of operations is $ [3, 2, 1] \xrightarrow{i_1=1} [3, 1, 2] \xrightarrow{i_2=2} [1, 3, 2] \xrightarrow{i_3=1} [1, 2, 3]. $ For the third example, one valid sequence of operations is $ [1, 5, 4, 3, 2] \xrightarrow{i_1=2} [5, 1, 3, 2, 4] \xrightarrow{i_2=2} [1, 5, 2, 4, 3] \xrightarrow{i_3=3} [2, 1, 5, 3, 4] \xrightarrow{i_4=2} [1, 2, 3, 4, 5] $ For the fourth example, one valid sequence of operations is $ [4, 3, 2, 1] \xrightarrow{i_1=1} [4, 2, 1, 3] \xrightarrow{i_2=3} [1, 4, 2 ,3] \xrightarrow{i_3=1} [1, 2, 3, 4] $