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.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		PrintWriter out = new PrintWriter(outputStream);
		InputReader in = new InputReader(inputStream);
		
//		for(int i=4;i<=4;i++) {
//			String f = i+".in";
//			InputStream uinputStream = new FileInputStream("1.in");
//			InputStream uinputStream = new FileInputStream(f);
//			InputReader in = new InputReader(uinputStream);
//			PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("shortcut.out")));
			Task t = new Task();
			t.solve(in, out);
			out.close();			
//		}
	}
	
	static class Task {		
		
		public void solve(InputReader in, PrintWriter out) throws IOException {
			int n = in.nextInt();
			ArrayList<Integer> odd = new ArrayList<Integer>();
			ArrayList<Integer> even = new ArrayList<Integer>();
			for(int i=0;i<n;i++) {
				int t = in.nextInt();
				if(t%2==0) even.add(t);
				else odd.add(t);
			}
			Collections.sort(odd, Collections.reverseOrder());
			Collections.sort(even, Collections.reverseOrder());
			if(odd.size()-even.size()>=2) {
				int sum = 0;
				for(int i=odd.size()-1;i>even.size();i--) sum+=odd.get(i);
				out.println(sum);
			}else if(even.size()-odd.size()>=2) {
				int sum = 0;
				for(int i=even.size()-1;i>odd.size();i--) sum+=even.get(i);
				out.println(sum);				
			}else {
				out.println(0);
			}
		}
	
		
	    public int numDupDigitsAtMostN(int N) {
	        // Transform N + 1 to arrayList
	        ArrayList<Integer> L = new ArrayList<Integer>();
	        for (int x = N + 1; x > 0; x /= 10)
	            L.add(0, x % 10);

	        // Count the number with digits < N
	        int res = 0, n = L.size();
	        for (int i = 1; i < n; ++i)
	            res += 9 * A(9, i - 1);

	        // Count the number with same prefix
	        HashSet<Integer> seen = new HashSet<>();
	        for (int i = 0; i < n; ++i) {
	            for (int j = i > 0 ? 0 : 1; j < L.get(i); ++j)
	                if (!seen.contains(j))
	                    res += A(9 - i, n - i - 1);
	            if (seen.contains(L.get(i))) break;
	            seen.add(L.get(i));
	        }
	        return N - res;
	    }


	    public int A(int m, int n) {
	        return n == 0 ? 1 : A(m, n - 1) * (m - n + 1);
	    }		
		
	    public int numDupDigitsAtMostN2(int N) {
	    	String x = N+"";
	    	int len = x.length();
	    	int ret = 0;
	    	for(int i=1;i<len;i++) {
	    		ret+=9*A(9,i-1);
	    	}
	    	boolean seen[] = new boolean[10];
	    	for(int i=0;i<len;i++) {
	    		int idx = x.charAt(i)-'0';
	            for (int j = i > 0 ? 0 : 1; j < idx; ++j)
	                if (!seen[j])
	                    ret += A(9-i, len - i - 1);
	            if (seen[idx]) break;
	            seen[idx] = true;;
	    	}
	    	return N-ret;
	    }
	    int find(int from, int to) {
	    	int c = 0;
	    	for(int i=from; i<=to;i++) {
	    		int t = i;
	    		boolean arr[] = new boolean[10];
	    		while(t>0) {
	    			int f = t%10;
	    			if(arr[f]) {
	    				c++;
	    				break;
	    			}
	    			else arr[f] = true;
	    			t/=10;
	    		}
	    	}
	    	return c;
	    }
	    public long fa(int a) {
	    	int v = 1;
	    	for(int i=a;i>=1;i--) v*=i;
	    	return v;
	    }
//	    public long A(int m, int n) {
//	    	return fa(n)/fa(n-m);
//	    }
	    public long C(int m, int n) {
	    	return A(m,n)/fa(m);
	    }
	}
	
	class BIT{
		int arr[];
		int n;
		public BIT(int a) {
			n=a;
			arr = new int[n];
		}
		int sum(int p) {
			int s=0;
			while(p>0) {
				s+=arr[p];
				p-=p&(-p);
			}
			return s;
		}
		void add(int p, int v) {
			while(p<n) {
				arr[p]+=v;
				p+=p&(-p);
			}
		}
	}
//	static class DSU{
//		int[] arr;
//		int[] sz;
//		public DSU(int n) {
//			arr = new int[n];
//			sz = new int[n];
//			for(int i=0;i<n;i++) arr[i] = i;
//			Arrays.fill(sz, 1);
//		}
//		public int find(int a) {
//			if(arr[a]!=a) arr[a] = find(arr[a]);
//			return arr[a];
//		}
//		public void union(int a, int b) {
//			int x = find(a);
//			int y = find(b);
//			if(x==y) return;
//			arr[x] = y;
//			sz[y] += sz[x];
//		}
//		public int size(int x) {
//			return sz[find(x)];
//		}
//	}	
	static class MinHeap<Key> implements Iterable<Key> {
		private int maxN;
		private int n;
		private int[] pq;
		private int[] qp;
		private Key[] keys;
		private Comparator<Key> comparator;
		
		public MinHeap(int capacity){
			if (capacity < 0) throw new IllegalArgumentException();
			this.maxN = capacity;
			n=0;
			pq = new int[maxN+1];
			qp = new int[maxN+1];
			keys = (Key[]) new Object[capacity+1];
			Arrays.fill(qp, -1);
		}
		
		public MinHeap(int capacity, Comparator<Key> c){
			if (capacity < 0) throw new IllegalArgumentException();
			this.maxN = capacity;
			n=0;
			pq = new int[maxN+1];
			qp = new int[maxN+1];
			keys = (Key[]) new Object[capacity+1];
			Arrays.fill(qp, -1);
			comparator = c;
		}			
		public boolean isEmpty()	{ return n==0; 	}
		public int size()			{ return n;		}
		public boolean contains(int i) {
	        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
	        return qp[i] != -1;
		}	
		public int peekIdx() {
	        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
	        return pq[1];		
		}	
		public Key peek(){
			if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");
			return keys[pq[1]];
		}
		public int poll(){
			if(isEmpty()) throw new NoSuchElementException("Priority queue underflow");
			int min = pq[1];
			exch(1,n--);
			down(1);
			assert min==pq[n+1];
			qp[min] = -1;
			keys[min] = null;		
			pq[n+1] = -1;
			return min;
		}
	    public void update(int i, Key key) {
	        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
	        if (!contains(i)) {
	        	this.add(i, key);
	        }else {
	        	keys[i] = key;
	        	up(qp[i]);
	        	down(qp[i]);
	        }
	    }	
		private void add(int i, Key x){
	        if (i < 0 || i >= maxN) throw new IllegalArgumentException();
	        if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
	        n++;
	        qp[i] = n;
	        pq[n] = i;
	        keys[i] = x;
	        up(n);
		}
		private void up(int k){
			while(k>1&&less(k,k/2)){
				exch(k,k/2);
				k/=2;
			}
		}
		private void down(int k){
			while(2*k<=n){
				int j=2*k;
				if(j<n&&less(j+1,j)) j++;
				if(less(k,j)) break;
				exch(k,j);
				k=j;
			}
		}
		
		public boolean less(int i, int j){
	        if (comparator == null) {
	            return ((Comparable<Key>) keys[pq[i]]).compareTo(keys[pq[j]]) < 0;
	        }
	        else {
	            return comparator.compare(keys[pq[i]], keys[pq[j]]) < 0;
	        }
		}

		public void exch(int i, int j){
	        int swap = pq[i];
	        pq[i] = pq[j];
	        pq[j] = swap;
	        qp[pq[i]] = i;
	        qp[pq[j]] = j;
		}

		@Override
		public Iterator<Key> iterator() {
			// TODO Auto-generated method stub
			return null;
		}
	}  	

    private static class InputReader
    {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int zcurChar;
        private int znumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream)
        {
            this.stream = stream;
        }

        public int read()
        {
            if (znumChars == -1)
                throw new InputMismatchException();
            if (zcurChar >= znumChars)
            {
            	zcurChar = 0;
                try
                {
                    znumChars = stream.read(buf);
                } catch (IOException e)
                {
                    throw new InputMismatchException();
                }
                if (znumChars <= 0)
                    return -1;
            }
            return buf[zcurChar++];
        }

        public int nextInt()
        {
            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 nextString()
        {
            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 double nextDouble()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.')
            {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.')
            {
                c = read();
                double m = 1;
                while (!isSpaceChar(c))
                {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public long nextLong()
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            long 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 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 nextString();
        }
        
        public int[] readarray(int n)
        {
        	int ret[] = new int[n];
        	for(int i=0;i<n;i++) ret[i] = this.nextInt();
        	return ret;
        }        

        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }    

	static class Dumper {
		static void print_int_arr(int[] arr) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_char_arr(char[] arr) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_double_arr(double[] arr) {
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_2d_arr(int[][] arr, int x, int y) {
			for (int i = 0; i < x; i++) {
				for (int j = 0; j < y; j++) {
					System.out.print(arr[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print_2d_arr(boolean[][] arr, int x, int y) {
			for (int i = 0; i < x; i++) {
				for (int j = 0; j < y; j++) {
					System.out.print(arr[i][j] + " ");
				}
				System.out.println();
			}
			System.out.println();
			System.out.println("---------------------");
		}

		static void print(Object o) {
			System.out.println(o.toString());
		}

		static void getc() {
			System.out.println("here");
		}
	}
}