まず、\(A\) の真ん中をまたぐ操作は禁止して良いです。なぜなら、\(A\) の真ん中をまたぐ操作は、またいだ部分で左右に分け短い方を折り返し長い方と相殺させることで真ん中をまたがない操作に変換することができるからです。

長さ \(\displaystyle N'=\left\lfloor \frac N2\right\rfloor\) の整数列 \(B=(B_1,B_2,\ldots,B_{N'})\) を \(B_i=(A_i - A_{N+1-i}) \bmod M\) と定義します。上の事実を用いることで、以下の問題に帰着することができます。

以下の操作を最小何回行うことで \(B\) の要素を全て \(0\) にすることができるか？

• \(1\le l\le r\le N'\) を満たす整数の組 \((l,r)\) と \(c \in \lbrace -1,1\rbrace\) を選び、\(i=l,l+1,\ldots,r\) に対し \(B_i\) を \((B_i+c) \bmod M\) に置き換える。

\(c=1\) は \(A\) の左側に対する操作、\(c=-1\) は右側に対する操作に対応します。

ここで、長さ \(N''=N'+1\) の整数列 \(C=(C_1,C_2,\ldots,C_{N''})\) を \(C_i=(B_{i}-B_{i-1}) \bmod M\) として定義します。ただし、\(B_0=B_{N'+1}=0\) とします。すると、\(i=l,l+1,\ldots,r\) に対し \(B_i\) を \((B_i+c) \bmod M\) に置き換える操作は \(C_{l}\) を \((C_{l}+c) \bmod M\) に、 \(C_{r+1}\) を \((C_{r+1}-c) \bmod M\) に置き換える操作に対応します。したがって、上の問題はさらに以下の問題に帰着することができます。

以下の操作を最小何回行うことで \(C\) の要素を全て \(0\) にすることができるか？

• \(1\le i,j\le N'',\ i\neq j\) を満たす整数の組 \((i,j)\) を選び、\(C_i\) を \((C_i+1) \bmod M\) に、\(C_j\) を \((C_j-1)\bmod M\) に置き換える。

\(C_i\) を \((C_i+1) \bmod M\) に置き換える操作を加算操作、\((C_i-1) \bmod M\) に置き換える操作を減算操作と呼びます。

\(i\neq j\) という条件を外しても答えは変わらないので、この条件を外して考えます。

\(i,j\) 独立に考えることで、加算操作と減算操作を同じ回数行うことで \(C\) の要素を全て \(0\) にすることができるか判定できれば良いです。

加算操作と減算操作を同じ index に対して行うことは無駄です。したがって、\(\empty \neq X\subsetneq \lbrace 1,2,\ldots,N''\rbrace\) を定め、\(i \in X\) なら \(C_i\) は加算操作のみ、\(i \not \in X\) なら \(C_i\) は減算操作のみ、と限定します。ただし、\(C_i=0\) を満たす \(i\) は \(X\) に含んでも含まなくても変わらないので、必ず含まないことにします。\(C\) の定め方より \(S=\sum C\) は必ず \(M\) の倍数なので、どのように \(X\) を定めて加算操作と減算操作に制限をかけても条件を満たす操作方法は必ず存在します。

このとき、加算操作に必要な操作回数は \(\displaystyle \sum_{i \not\in X}(M-C_i)\) 回、減算操作に必要な回数は \(\displaystyle \sum_{i\in X}C_i\) 回となります。したがって、操作回数は \(\displaystyle \max\left(\sum_{i \not\in X}(M-C_i),\sum_{i\in X}C_i\right)\) 回と表されます。 \(\displaystyle S_X=\sum_{i \in X} C_i\) とすると、この式は \(\displaystyle S_X+M\max\left(N''-|X|-\frac{S}{M} ,0\right)\) と表されます。\(X\) は要素数と要素の総和しか影響しないので、要素数 \(k\) を固定した場合 \(C\) の値が小さい順に \(k\) 個取ることが最適です。さらに、要素数を \(1\) 増やした場合、\(S_X\) の値は \(0\) 以上 \(M\) 未満増えます。一方、 \(\displaystyle M\max\left(N''-|X|-\frac{S}{M} ,0\right)\) は \(\displaystyle |X| < N''-\frac SM\) の場合 \(M\) 減りますが、そうでない場合は変わりません。したがって、操作回数を最小にする場合は \(\displaystyle |X|=N''-\frac SM\) の場合で、この場合 \(\max\) 関数の \(2\) つの引数の値は一致するので操作回数は \(C\) の要素の小さい順に \(|X|\) 個の総和となります。

以上を適切に実装することでこの問題に正答することができます。計算量はソートがボトルネックとなり \(O(N\log N)\) です。

実装例(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]))