D. Constant Palindrome Sum
brute force; data structures; greedy; two pointers
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.