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
"""
- math -
from math import factorial
from math import gcd
from math import pi
large_p = 10**9 + 7
from itertools import accumulate # 累積和
from operator import mul
- other -
from collections import Counter
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
from operator import itemgetter
from functools import reduce
- list -
from copy import deepcopy
from collections import deque
from heapq import heapify, heappop, heappush
- output -
p2d = lambda x: print(*x, sep="\n")
p2line = lambda x: print(*x, sep=" ")
print(*list1, sep="\n")
- input -
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
= map(int, input().split())
= [tuple(map(int, input().split())) for _ in range(n)]
m = map(int, read().split()) /ab = zip(m, m) /for a, b in ab:
ps = [line.split() for line in readlines()] # inputの最後まで読んでしまうので注意。
n, k, *h = map(int, read().split())
a = tuple(map(int, readlines()))
- run -
sys.setrecursionlimit(10**6)
from time import sleep
from numba import njit
"""
# ATC05

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n = int(input())
    o = []
    e = []
    m = map(int, read().split())
    for a in m:
        if a&1:
            o.append(a)
        else:
            e.append(a)
    sumall = sum(o) + sum(e)
    o.sort(reverse=True)
    e.sort(reverse=True)
    leno = len(o)
    lene = len(e)
    if leno == lene:
        print(0)
    elif leno < lene:
        r = sumall - sum(e[:leno+1]) - sum(o)
        print(r)
    else:
        r = sumall - sum(o[:lene+1]) - sum(e)
        print(r)


if __name__ == '__main__':
    main()
