D. Constant Palindrome Sum

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa consisting of nn integers (it is guaranteed that nn is even, i.e. divisible by 22). All aiai does not exceed some integer kk.

Your task is to replace the minimum number of elements (replacement is the following operation: choose some index ii from 11 to nn and replace aiai with some integer in range [1;k][1;k]) to satisfy the following conditions:

  • after all replacements, all aiai are positive integers not greater than kk;
  • for all ii from 11 to n2n2 the following equation is true: ai+an−i+1=xai+an−i+1=x, where xx should be the same for all n2n2 pairs of elements.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases. Then tt test cases follow.

The first line of the test case contains two integers nn and kk (2≤n≤2⋅105,1≤k≤2⋅1052≤n≤2⋅105,1≤k≤2⋅105) — the length of aa and the maximum possible value of some aiai correspondingly. It is guratanteed that nn is even (i.e. divisible by 22). The second line of the test case contains nnintegers a1,a2,…,ana1,a2,…,an (1≤ai≤k1≤ai≤k), where aiai is the ii-th element of aa.

It is guaranteed that the sum of nn (as well as the sum of kk) over all test cases does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105, ∑k≤2⋅105∑k≤2⋅105).

Output

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

Example

input

Copy

4
4 2
1 2 1 2
4 3
1 2 2 1
8 7
6 1 1 7 6 3 4 6
6 6
5 2 6 1 3 4

output

Copy

0
1
4
2

题意：

给一个 n 个数的数组，每个数都在[1, k]之间，每次可以将一个数替换为[1, k]中的某个数，求最少替换次数使得

（1）数组中的每个数都在[1, k]之间

（2）对于每个 i ，有a[i] + a[n - i + 1]  = x 相同

思路：

用差分数组维护取某个定值时的操作数

由于1 <= a[i] <= k，则2 <= x <= 2 * k

对于每一对a[i]，a[n - i + 1]，minn = min(a[i], a[n - i + 1])，maxx = max(a[i], a[n - i + 1])；

（1）两个数的和正好是 x，不需要修改

（2）如果2 <= x <= minn，修改一个后，两个数的和仍然大于x，所以两个都应该修改。

（3）如果max + k + 1 <= x <= 2 * k，修改较小的一个后，两个数的和仍然小于x，所以两个都应该修改

（4）其他情况修改一个数就可以

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1.0);
const int N = 2e5 + 10;

int x[2 * N], a[N];

int main()
{
    int n, k, t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &k);
        memset(x, 0, sizeof(x));
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a[i]);
        }
        for(int i = 1; i <= n / 2; ++i)
        {
            int minn = min(a[i], a[n - i + 1]);
            int maxx = max(a[i], a[n - i + 1]);
            int sum = a[i] + a[n - i + 1];
            x[2] += 2;
            x[minn + 1]--;
            x[maxx + k + 1]++;
            x[2 * k + 1] -= 2;
            x[sum]--;
            x[sum + 1]++;
        }
        int ans = x[2];
        for(int i = 3; i <= 2 * k; ++i)
        {
            x[i] += x[i - 1];
            ans = min(ans, x[i]);
        }
        cout<<ans<<'\n';
    }
    return 0;
}