RT

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 100;
int n;
int a[maxn];
int j[maxn], o[maxn];
int l1 = 1, l2 = 1, r1, r2;
long long ans;

int yes(int x)
{
    if(x & 1 == 1)return -1;
    return 1;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        if(a[i] & 1 == 1)
        {
            r1 ++;
            j[r1] = a[i];
        }
        else
        {
            r2 ++;
            o[r2] = a[i];
        }
    }
    sort(j + 1, j + r1 + 1);
    sort(o + 1, o + r2 + 1);
    long long cnt = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(i % 2 == 1)
        {
            if(r2 - l2 >= 0)
            {
                ans += o[r2] + cnt;
                cnt += o[r2];
                r2 --;
            }
            else
            {
                ans += j[l1] * (-1) + cnt;
                cnt += -j[l1];
                l1 ++;
            }
        }
        else
        {
            if(r1 - l1 >= 0)
            {
                ans += j[r1] + cnt;
                cnt += j[r1];
                r1 --;
            }
            else
            {
                ans += o[l2] * (-1) + cnt;
                cnt += -o[l2];
                l2 ++;
            }
        }
    }
    printf("%lld\n", ans);
}