First, we may forbid an operation that strides the middle of \(A\), because any such operation can be transformed into an operation that does not stride the middle by cancelling out either the prefix or suffix whose center is at the middle of \(A\).

Define an integer sequence \(B=(B_1,B_2,\ldots,B_{N'})\) of length \(\displaystyle N'=\left\lfloor \frac N2\right\rfloor\) as \(B_i=(A_i - A_{N+1-i}) \bmod M\). By the fact above, the problem is transformed into the following:

How many times do we need to apply the following operation to \(B\) to make all elements \(0\)?

• Choose an integer pair \((l,r)\) with \(1\le l\le r\le N'\) and \(c \in \lbrace -1,1\rbrace\), and replace \(B_i\) with \((B_i+c) \bmod M\) for each \(i=l,l+1,\ldots,r\).

\(c=1\) corresponds to an operation on the left part of \(A\), and \(c=-1\) on the right.

Let us define an integer sequence \(C=(C_1,C_2,\ldots,C_{N''})\) of length \(N''=N'+1\) as \(C_i=(B_{i}-B_{i-1}) \bmod M\), where we define \(B_0=B_{N'+1}=0\). Then replacing \(B_i\) with \((B_i+c) \bmod M\) for each \(i=l,l+1,\ldots,r\) is equivalent to setting \(C_{l}\) to \((C_{l}+c) \bmod M\), and \(C_{r+1}\) to \((C_{r+1}-c) \bmod M\). Thus, the problem above is further reduced to the following:

How many times do we need to apply the following operation to \(B\) to make all elements \(0\)?

• Choose an integer pair \((,j)\) with \(1\le i,j\le N'',\ i\neq j\), and replace \(C_i\) with \((C_i+1) \bmod M\) and \(C_j\) with \((C_j-1)\bmod M\).

Let us call a replacement of \(C_i\) into \((C_i+1) \bmod M\) an increment, and \((C_i-1) \bmod M\) a decrement operation.

Ignore the condition \(i\neq j\) does not change the answer, so we will ignore it from now on.

By considering \(i\) and \(j\) independently, it suffices to determine whether we can perform increments and decrements the same number of times to make all elements of \(C\) zero.

It is useless to apply increments and decrements on the same element, so we define \(\empty \neq X\subsetneq \lbrace 1,2,\ldots,N''\rbrace\), and apply only increments to \(C_i\) if \(i \in X\) and only decrements if \(i \not \in X\). Whether \(i\) with \(C_i=0\) is contained in \(X\) does not affect to the answer, so we decide not to include them. By definition of \(C\), the sum \(S=\sum C\) is always a multiple of \(M\), so no matter which \(X\) we choose to impose constraints on increments and decrements, there always exist a sequence of operation to achieve the goal.

In this case, the numbers of increments and decrements required are \(\displaystyle \sum_{i \not\in X}(M-C_i)\) and \(\displaystyle \sum_{i\in X}C_i\) required, respectively. Thus, the number of operations is \(\displaystyle \max\left(\sum_{i \not\in X}(M-C_i),\sum_{i\in X}C_i\right)\). If we define \(\displaystyle S_X=\sum_{i \in X} C_i\), this expression is written as \(\displaystyle S_X+M\max\left(N''-|X|-\frac{S}{M} ,0\right)\). What only matters is the number of elements and sum of elements of \(X\), so when the number of elements \(k\) is fixed, it is optimal to pick the smallest \(k\) elements of \(C\). Moreover, increasing the number of element by one increases \(S_X\) by at least \(0\) and at most \(M-1\). On the other hand, \(\displaystyle M\max\left(N''-|X|-\frac{S}{M} ,0\right)\) decreases by \(M\) if \(\displaystyle |X| < N''-\frac SM\), and remain the same otherwise. Thus, the number of operations is minimized when \(\displaystyle |X|=N''-\frac SM\), in which case the two arguments of \(\max\) function take the same value. Hence, the number of operations equals the sum of the \(|X|\) smallest values of \(C\).

The problem can be solved by appropriately implementing this. The time complexity is \(O(N\log N)\), where sorting is the bottleneck.

Sample code (Python)

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = [0] + [(a[i] - a[n - 1 - i]) % m for i in range(n // 2)] + [0]
    c = [(b[i + 1] - b[i]) % m for i in range(len(b) - 1)]
    c.sort()
    print(sum(c[:len(c) - sum(c) // m]))