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.BufferedWriter;
	import java.io.IOException;
	import java.io.InputStream;
	import java.io.OutputStream;
	import java.io.OutputStreamWriter;
	import java.io.PrintWriter;
	import java.io.Writer;
	import java.util.Arrays;
	import java.util.InputMismatchException;
	import java.util.*;
	import java.io.*;
	import java.math.*;
	public class Main7{

	static class Pair
		{ 
			int x; 
			int y;
			public Pair(int x, int y) 
			{	 
				this.x = x; 
				this.y = y; 
			}	 
		} 
		static class Compare
		{ 
			static void compare(Pair arr[], int n) 
			{ 
				// Comparator to sort the pair according to second element 
				Arrays.sort(arr, new Comparator<Pair>() { 
					@Override public int compare(Pair p1, Pair p2) 
					{ 
						if(p1.x>p2.x)
						{
							return 1;
						}
						else if(p2.x>p1.x)
						{
							return -1;
						}
						else
						{
							if(p1.y>p2.y)
							{
								return 1;
							}
							else if(p1.y<p2.y)
							{
								return -1;
							}
							else
								return 0;
						} 
					} 
				}); 
			} 
		}
		public static long pow(long a, long b)
		{
			long result=1;
			while(b>0)
			{
				if (b % 2 != 0)
				{
					result=(result*a)%998244353;
					b--;
				} 
				a=(a*a)%998244353;
				b /= 2;
			}   
			return result;
		}
		public static long fact(long num)
		{
					long value=1;
					int i=0;
					for(i=2;i<num;i++)
					{
						value=((value%mod)*i%mod)%mod;
					}
					return value;
				}
				public static int gcd(int a, int b)
				{
					if (a == 0)
						return b;
					return gcd(b%a, a);
				}
				
				public static long lcm(int a,int b)
				{
					return a * (b / gcd(a, b));
				}
				public static long sum(int h)
				{
					return (h*(h+1)/2);
				}
				public static void dfs(int parent,boolean[] visited)
				{
					ArrayList<Integer> arr=new ArrayList<Integer>();
					arr=graph.get(parent);
					visited[parent]=true;
					for(int i=0;i<arr.size();i++)
					{
						int num=arr.get(i);
						if(visited[num]==false)
						{
							dfs(num,visited);
							if(c[num]==1)
							{
								count[parent]++;
							}
						}
					}
					if(count[parent]==graph.get(parent).size() && c[parent]==1)
					{
						flag[parent]=1;
					}
				}
				static int[] flag;
				static int[] c;
				static int[] count;
				static ArrayList<Integer> ar3;
				static long mod=1000000007L;
				static ArrayList<ArrayList<Integer>> graph;
				
				public static void main(String args[])throws IOException
				{
				//	InputReader in=new InputReader(System.in);
				//	OutputWriter out=new OutputWriter(System.out);
				//	long a=pow(26,1000000005);
				    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
					ArrayList<Integer> ar=new ArrayList<>();
					ArrayList<Integer> even=new ArrayList<>();
						ArrayList<Integer> odd=new ArrayList<>();
					ArrayList<Integer> ar4=new ArrayList<>();
					TreeSet<Integer> ts=new TreeSet<>();
					TreeSet<String> pre=new TreeSet<>();
				//	HashMap<Long,Long> hash=new HashMap<>();
					//HashMap<Long,Integer> hash1=new HashMap<Long,Integer>();
					HashMap<Integer,Integer> hash2=new HashMap<Integer,Integer>();
				/*	boolean[] prime=new boolean[10001];
					for(int i=2;i*i<=10000;i++)
					{
						if(prime[i]==false)
						{
							for(int j=2*i;j<=10000;j+=i)
							{
								prime[j]=true;fv
								
							}
						}
					}*/
					int n=i();
					int[] a=new int[n];
					long sum=0;
					for(int i=0;i<n;i++)
					{
						a[i]=i();
						ar.add(a[i]);
						sum+=a[i];
					}
					Collections.sort(ar);
					for(int i=0;i<n;i++)
					{
						a[i]=ar.get(i);
						if(a[i]%2==1)
						{
							odd.add(a[i]);
						}
						else
							even.add(a[i]);
					}
					Collections.sort(even);
					Collections.sort(odd);
					
					long ans=0,ans1=0;
					int k=odd.size()-1;
					for(int i=even.size()-1;i>=0;i--)
					{
						ans+=even.get(i);
						if(k==-1)
						{
							break;
						}
						if(k>=0)
						{
							ans+=odd.get(k);
							k--;
						}
					}
					long value=sum-ans;
					k=even.size()-1;
					for(int i=odd.size()-1;i>=0;i--)
					{
						ans1+=odd.get(i);
						if(k==-1)
						{
							break;
						}
						if(k>=0)
						{
							ans1+=even.get(k);
							k--;
						}
					}
					long value1=sum-ans1;
					pln(Math.min(value,value1)+"");
				}
					 
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				
				/**/
				static InputReader in=new InputReader(System.in);
					static OutputWriter out=new OutputWriter(System.out);
					public static long l()
					{
						String s=in.String();
						return Long.parseLong(s);
					}
					public static void pln(String value)
					{
						System.out.println(value);
					}
					public static int i()
					{
						return in.Int();
					}
					public static String s()
					{
						return in.String();
					}
		}
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			 
			class InputReader {
				 
				private InputStream stream;
				private byte[] buf = new byte[1024];
				private int curChar;
				private int numChars;
				private SpaceCharFilter filter;
			 
				public InputReader(InputStream stream) {
					this.stream = stream;
				}
			 
				public int read() {
					if (numChars== -1)
						throw new InputMismatchException();
					if (curChar >= numChars) {
						curChar = 0;
						try {
							numChars = stream.read(buf);
						} catch (IOException e) {
							throw new InputMismatchException();
						}
						if (numChars <= 0)
							return -1;
					}
					return buf[curChar++];
				}
			 
				public int Int() {
					int c = read();
					while (isSpaceChar(c))
						c = read();
					int sgn = 1;
					if (c == '-') {
						sgn = -1;
						c = read();
					}
					int res = 0;
					do {
						if (c < '0' || c > '9')
							throw new InputMismatchException();
						res *= 10;
						res += c - '0';
						c = read();
					} while (!isSpaceChar(c));
					return res * sgn;
				}
			 
				public String String() {
					int c = read();
					while (isSpaceChar(c))
						c = read();
					StringBuilder res = new StringBuilder();
					do {
						res.appendCodePoint(c);
						c = read();
					} while (!isSpaceChar(c));
					return res.toString();
				}
			 
				public boolean isSpaceChar(int c) {
					if (filter != null)
						return filter.isSpaceChar(c);
					return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
				}
			 
				public String next() {
					return String();
				}
			 
				public interface SpaceCharFilter {
					public boolean isSpaceChar(int ch);
				}
			}
			 
			class OutputWriter {
				private final PrintWriter writer;
			 
				public OutputWriter(OutputStream outputStream) {
					writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
				}
			 
				public OutputWriter(Writer writer) {
					this.writer = new PrintWriter(writer);
				}
			 
				public void print(Object...objects) {
					for (int i = 0; i < objects.length; i++) {
						if (i != 0)
							writer.print(' ');
						writer.print(objects[i]);
					}
				}
			 
				public void printLine(Object...objects) {
					print(objects);
					writer.println();
				}
			 
				public void close() {
					writer.close();
				}
			 
				public void flush() {
					writer.flush();
				}
			 
				}
			 
				class IOUtils {
			 
				public static int[] readIntArray(InputReader in, int size) {
					int[] array = new int[size];
					for (int i = 0; i < size; i++)
						array[i] = in.Int();
					return array;
				}
			 
				} 