$O(N)$

条件分析： 要使 min(a) + max(a) 为偶数，有两种情况：

两个数都是偶数

两个数都是奇数

关键观察：

如果原数组已经满足条件，则不需要删除任何元素（操作次数为0）。

否则，我们需要通过删除元素来调整数组的最小值和最大值，使得它们的和为偶数。

策略选择：

如果当前数组的最小值和最大值之和已经是偶数，直接返回0。

否则，考虑删除最小值或最大值来改变条件：

删除最小值：新的最小值是次小值

删除最大值：新的最大值是次大值

贪心策略：

由大到小依次删除数字，直到剩余数组满足条件。计算删除个数 $x$ .

由小到大依次删除数字，直到剩余数组满足条件。计算删除个数 $y$ .

答案为 $min(x,y)$ .

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 2e5 + 10, M = 25;

int a[N];

void solve()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sort(a + 1, a + n + 1);
    
    int l = 1, r = n;
    while(l <= n && (a[l] + a[n]) % 2 != 0) l ++;
    while(r > 0 && (a[r] + a[1]) % 2 != 0) r --;
    
    cout << min(l - 1, n - r) << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while(t --)
        solve();
}