Polycarp has an array a consisting of n integers.

He wants to play a game with this array. The game consists of several moves. On the first move he chooses any element and deletes it (after the first move the array contains n-1 elements). For each of the next moves he chooses any element with the only restriction: its parity should differ from the parity of the element deleted on the previous move. In other words, he alternates parities (even-odd-even-odd-... or odd-even-odd-even-...) of the removed elements. Polycarp stops if he can't make a move.

Formally: 

  * If it is the first move, he chooses any element and deletes it; 
  * If it is the second or any next move: 
    * if the last deleted element was odd, Polycarp chooses any even element and deletes it; 
    * if the last deleted element was even, Polycarp chooses any odd element and deletes it. 
  * If after some move Polycarp cannot make a move, the game ends. 



Polycarp's goal is to minimize the sum of non-deleted elements of the array after end of the game. If Polycarp can delete the whole array, then the sum of non-deleted elements is zero.

Help Polycarp find this value.

Input

The first line of the input contains one integer n (1 ≤ n ≤ 2000) — the number of elements of a.

The second line of the input contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^6), where a_i is the i-th element of a.

Output

Print one integer — the minimum possible sum of non-deleted elements of the array after end of the game.

Examples

Input


5
1 5 7 8 2


Output


0


Input


6
5 1 2 4 6 3


Output


0


Input


2
1000000 1000000


Output


1000000
#include <bits/stdc++.h>
long long mod = 1e9 + 7;
using namespace std;
void primeFactors(long long n, vector<long long> &vec) {
  while (n % 2 == 0) {
    vec.push_back(2);
    n = n / 2;
  }
  for (long long i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      vec.push_back(i);
      n = n / i;
    }
  }
  if (n > 2) {
    vec.push_back(n);
  }
}
long long gcd(long long a, long long b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}
long long Lcm(long long a, long long b) { return ((a * b) / gcd(a, b)); }
tuple<long long, long long, long long> getL(complex<long double> p1,
                                            complex<long double> p2) {
  long long a, b, c;
  a = p2.imag() - p1.imag();
  b = p1.real() - p2.real();
  c = -a * p1.real() - b * p1.imag();
  long long gcdres = abs(gcd(a, gcd(b, c)));
  if (a < 0 || a == 0 && b < 0) {
    gcdres *= -1;
  }
  a /= gcdres;
  b /= gcdres;
  c /= gcdres;
  return tuple<long long, long long, long long>(a, b, c);
}
long long fastpow(long long base, long long pow) {
  if (!base) return 0;
  if (!pow) return 1;
  if (pow == 1) return base;
  long long x = fastpow(base, pow / 2) % mod;
  x *= x;
  x %= mod;
  if (pow % 2) x *= base;
  return x % mod;
}
long long inverse(long long x) { return fastpow(x, mod - 2) % mod; }
long double disty(pair<long long, long long> a, pair<long long, long long> b) {
  return sqrt(pow(b.second - a.second, 2) + pow(b.first - a.first, 2));
}
void factorize(long long x, set<long long> &ss) {
  while (x % 2 == 0) ss.insert(2), x /= 2;
  for (int i = 3; i <= sqrt(x); i += 2)
    while (x % i == 0) ss.insert(i), x /= i;
  if (x > 2) ss.insert(x);
}
void SieveOfEratosthenes(long long n, bool prime[]) {
  for (int p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (int i = p * p; i <= n; i += p) prime[i] = false;
    }
  }
}
void divisors(long long n, vector<long long> &vec) {
  for (long long i = 2; i <= sqrt(n); ++i) {
    if (n % i == 0 && i != sqrt(n)) {
      vec.push_back(i);
      vec.push_back(n / i);
    } else if (n % i == 0) {
      vec.push_back(i);
    }
  }
}
bool isprime(long long n) {
  if (n == 1) {
    return false;
  }
  for (int i = 2; i <= sqrt(n); ++i) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}
complex<long double> rot(complex<long double> p, long double angle) {
  return (p * polar((long double)1.0, angle));
}
complex<long double> rotA(complex<long double> p, complex<long double> A,
                          long double angle) {
  return (((p - A) * polar((long double)1, angle)) + A);
}
long double distance(complex<long double> a, complex<long double> b) {
  long double x1 = a.real(), y1 = a.imag(), x2 = b.real(), y2 = b.imag();
  return pow(y2 - y1, 2) + pow(x2 - x1, 2);
}
int distSq(pair<long long, long long> p, pair<long long, long long> q) {
  return (p.first - q.first) * (p.first - q.first) +
         (p.second - q.second) * (p.second - q.second);
}
bool isSquare(pair<long long, long long> p1, pair<long long, long long> p2,
              pair<long long, long long> p3, pair<long long, long long> p4) {
  long long d2 = distSq(p1, p2);
  long long d3 = distSq(p1, p3);
  long long d4 = distSq(p1, p4);
  if (d2 == d3 && 2 * d2 == d4 && 2 * d2 == distSq(p2, p3)) {
    int d = distSq(p2, p4);
    return (d == distSq(p3, p4) && d == d2);
  }
  if (d3 == d4 && 2 * d3 == d2 && 2 * d3 == distSq(p3, p4)) {
    int d = distSq(p2, p3);
    return (d == distSq(p2, p4) && d == d3);
  }
  if (d2 == d4 && 2 * d2 == d3 && 2 * d2 == distSq(p2, p4)) {
    int d = distSq(p2, p3);
    return (d == distSq(p3, p4) && d == d2);
  }
  return false;
}
long long FP(long long base, long long power, long long m) {
  if (power == 0) {
    return 1;
  } else if (power % 2 == 0) {
    long long res = FP(base, power / 2, m);
    return (res % m * res % m) % m;
  } else {
    long long res = FP(base, power / 2, m);
    return ((((base % m * (res % m)) % m) * (res % m) % m) % m);
  }
}
long long EGCD(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 0;
    y = 1;
    return a;
  } else {
    long long ans = EGCD(b, a % b, x, y);
    long long tmp = x;
    x = y - (a / b) * x;
    y = tmp;
    return ans;
  }
}
long long factorial(long long n) {
  if (n == 0) {
    return 1;
  } else
    return n * factorial(n - 1);
}
int main() {
  long long n;
  priority_queue<long long> odd, even, odd2, even2;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    long long entry;
    cin >> entry;
    if (entry % 2 == 0) {
      even.push(entry);
    } else {
      odd.push(entry);
    }
  }
  even2 = even;
  odd2 = odd;
  long long z = 0, x = 0;
  while (!odd.empty() && !even.empty()) {
    if (z % 2 == 0) {
      even.pop();
    } else {
      odd.pop();
    }
    z += 1;
  }
  while (!odd2.empty() && !even2.empty()) {
    if (x % 2 == 0) {
      odd2.pop();
    } else {
      even2.pop();
    }
    x += 1;
  }
  if (z % 2 == 0 && !even.empty()) {
    even.pop();
  } else if (z % 2 != 0 && !odd.empty()) {
    odd.pop();
  }
  if (x % 2 == 0 && !odd2.empty()) {
    odd2.pop();
  } else if (x % 2 != 0 && !even2.empty()) {
    even2.pop();
  }
  long long sum = 0, othersum = 0;
  while (!even.empty()) {
    sum += even.top();
    even.pop();
  }
  while (!odd.empty()) {
    sum += odd.top();
    odd.pop();
  }
  while (!odd2.empty()) {
    othersum += odd2.top();
    odd2.pop();
  }
  while (!even2.empty()) {
    othersum += even2.top();
    even2.pop();
  }
  cout << min(sum, othersum) << "\n";
  return 0;
}
