Transforming the expression to be minimized, we get the following:

\[ \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} \]

Since \(\displaystyle \sum_{i=1}^N A_i \) is constant regardless of the rearrangement, it suffices to maximize \(\displaystyle A_1+A_N+\sum_{i=1}^{N-1}((A_i+A_{i+1})\bmod 2)\).

When the parities of \(A_1\) and \(A_N\) are fixed, it suffices to set \(A_1\) and \(A_N\) to the largest values among those with the fixed parities (if the parities are the same, take the largest and second largest values). Furthermore, once the parities of \(A_1\) and \(A_N\) are fixed, the maximum value of \(\displaystyle \sum_{i=1}^{N-1}((A_i+A_{i+1})\bmod 2)\) can also be easily computed, so it suffices to compute it for each case.

Sample implementation (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)