最小化する値を式変形すると以下のようになります。

\[ \begin{aligned} &\phantom{=}\sum_{i=1}^{N-1}\left\lfloor\frac{A_i+A_{i+1}}2 \right\rfloor\\ &=\frac12\sum_{i=1}^{N-1}\left(A_i+A_{i+1}-((A_i+A_{i+1})\bmod 2)\right)\\ &=\sum_{i=1}^N A_i - \frac12\left(A_1+A_N+\sum_{i=1}^{N-1}((A_i+A_{i+1})\bmod 2)\right)\\ \end{aligned} \]

\(\displaystyle \sum_{i=1}^N A_i \) は並べ替えによらず一定なので、\(\displaystyle A_1+A_N+\sum_{i=1}^{N-1}((A_i+A_{i+1})\bmod 2)\) を最大化すれば良いです。

\(A_1,A_N\) の偶奇を固定した際、\(A_1,A_N\) は固定した偶奇の中で最大のもの（偶奇が同じ場合は最大・\(2\) 番目に大きい値）にすれば良いです。さらに、\(A_1,A_N\) の偶奇が固定された中で \(\displaystyle \sum_{i=1}^{N-1}((A_i+A_{i+1})\bmod 2)\) の最大値も簡単に計算できるので、それぞれの最大値を計算すれば良いです。

実装例(Python3)

import sys

input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    a0 = []
    a1 = []
    for v in a:
        if v % 2 == 1:
            a1.append(v)
        else:
            a0.append(v)
    a0.sort(reverse=True)
    a1.sort(reverse=True)
    ans = 0
    if len(a0) >= 2:
        x, y = len(a0) - 2, len(a1)
        res = 2 * min(x, y) + 2 * (x < y)
        ans = max(ans, a0[0] + a0[1] + res)
    if len(a1) >= 2:
        x, y = len(a1) - 2, len(a0)
        res = 2 * min(x, y) + 2 * (x < y)
        ans = max(ans, a1[0] + a1[1] + res)
    if len(a0) >= 1 and len(a1) >= 1:
        x, y = len(a0) - 1, len(a1) - 1
        res = 2 * min(x, y) + 1
        ans = max(ans, a0[0] + a1[0] + res)
    assert ans % 2 == 0
    print(sum(a) - ans // 2)