1343D.md (1880B)
1 Source: https://codeforces.com/problemset/problem/1343/D 2 3 D. Constant Palindrome Sum 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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: 24 25 * after all replacements, all $a_i$ are positive integers not greater than $k$; 26 * 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. 27 28 You have to answer $t$ independent test cases. 29 30 Input 31 32 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. 33 34 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$. 35 36 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$). 37 38 Output 39 40 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. 41 42 Example 43 44 Input 45 46 ``` 47 4 48 4 2 49 1 2 1 2 50 4 3 51 1 2 2 1 52 8 7 53 6 1 1 7 6 3 4 6 54 6 6 55 5 2 6 1 3 4 56 ``` 57 58 Output 59 60 ``` 61 0 62 1 63 4 64 2 65 ```