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


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class sxz {

	static final int VISITED = 2, EXPLORED = 1, UNVISITED = 0;
	static ArrayList<Integer>[] adjList;
	static boolean[]  adjMat[];
	static int []visited;
	static int V;
	
	static boolean bfs(int s,int t,int w)
	{
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(s);
		int z=1;
		visited[s] = z;
		while(!q.isEmpty())
		{
			z++;
			int u = q.remove();
			for(int i=0;i<V;i++) {
				if(adjMat[u][i]) {
					int v=i;
					if(v==t) {
	//					System.out.println(visited[w]+" "+z);
						if(visited[w]!=0&&visited[w]!=z) {
			//				System.out.println(s+" "+w+" "+t+" "+true);
							return true;
						}
						else {
				//			System.out.println(false);
							return false;
						}
					}
					if(visited[v]==0)
					{
						visited[v] =z;
						q.add(v);
					}
				}
			}
		}
		return false;
	}
	/*
	static void dfs(int u)				//O(V + E) adjList, O(V^2) adjMat	
	{
		visited[u] = true;

	/*	//for adjacency list
		for(int v: adjList[u])
			if(!visited[v])
				dfs(v);*/

		//for adjacency matrix
	/*	for(int i = 0; i < V; ++i)
			if(adjMat[u][i] && !visited[i])
				dfs(i);
	}
	*/
	
	static ArrayList<Integer>[] a;
	static HashSet<Integer>[] h;
	static int m;
	static int hash(ArrayList<Integer> b) {
		int max=0;
		int sum=0;
		int min=0;
		for (int x:b) {
			max=Math.max(max,x);
			min=Math.max(x,min);
			sum+=x;
		}
		return max*sum+max+min;
	}
	static ArrayList<Integer> com(int idx, ArrayList<Integer> b) {
		ArrayList<Integer> ans = new ArrayList<>();
		for (int x : b) {
			if (h[idx].contains(x))
				ans.add(x);
		}
		return ans;
	}
 
	static int memo[][][];
	static int dfs(int idx, ArrayList<Integer> b) {
		if (idx == m)
			return b.size();
		int q=hash(b);
		if(memo[idx][b.size()][q]!=-1)
			return memo[idx][b.size()][q];
		int t = 1 + dfs(idx + 1, com(idx, b));
		int l = dfs(idx + 1, b);
		return memo[idx][b.size()][q]=Math.max(t, l);
	}
 
	static long gcd(long a, long b) 
    { 
    if (a == 0) 
        return b;  
    return gcd(b % a, a);  
    } 
      
    // method to return LCM of two numbers 
    static long lcm(long a, long b) 
    { 
        return (a*b)/gcd(a, b); 
    } 
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
			int n = Integer.parseInt(br.readLine());
			StringTokenizer st=new StringTokenizer(br.readLine());
			ArrayList<Integer> e=new ArrayList<>();
			ArrayList<Integer> o=new ArrayList<>();
			for (int i = 0; i < n; i++) {
				int x=Integer.parseInt(st.nextToken());
				if(x%2==0)
					e.add(x);
				else
					o.add(x);
			}
			Collections.sort(e);
			Collections.sort(o);
			int x=Math.abs(e.size()-o.size());
			if(x==0||x==1)
				pw.print(0);
			else {
				int s=0;
				if(e.size()>o.size()) {
					x=e.size()-o.size()-1;
					for (int i = 0; i < x; i++) {
						s+=e.get(i);
					}
				}
				else {
					x=o.size()-e.size()-1;
					for (int i = 0; i < x; i++) {
						s+=o.get(i);
					}
				}
				pw.print(s);	
			}
		pw.flush();
	}
}