CF1343D Constant Palindrome Sum

You are given an array $ a $ consisting of $ n $ integers (it is guaranteed that $ n $ is even, i.e. divisible by $ 2 $ ). All $ a_i $ does not exceed some integer $ k $ . Your task is to replace the minimum number of elements (replacement is the following operation: choose some index $ i $ from $ 1 $ to $ n $ and replace $ a_i $ with some integer in range $ [1; k] $ ) to satisfy the following conditions: - after all replacements, all $ a_i $ are positive integers not greater than $ k $ ; - for all $ i $ from $ 1 $ to $ \frac{n}{2} $ the following equation is true: $ a_i + a_{n - i + 1} = x $ , where $ x $ should be the same for all $ \frac{n}{2} $ pairs of elements. You have to answer $ t $ independent test cases.

The first line of the input contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Then $ t $ test cases follow. The first line of the test case contains two integers $ n $ and $ k $ ( $ 2 \le n \le 2 \cdot 10^5, 1 \le k \le 2 \cdot 10^5 $ ) — the length of $ a $ and the maximum possible value of some $ a_i $ correspondingly. It is guratanteed that $ n $ is even (i.e. divisible by $ 2 $ ). The second line of the test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le k $ ), where $ a_i $ is the $ i $ -th element of $ a $ . It is guaranteed that the sum of $ n $ (as well as the sum of $ k $ ) over all test cases does not exceed $ 2 \cdot 10^5 $ ( $ \sum n \le 2 \cdot 10^5 $ , $ \sum k \le 2 \cdot 10^5 $ ).

For each test case, print the answer — the minimum number of elements you have to replace in $ a $ to satisfy the conditions from the problem statement.