You are given n chips on a number line. The i-th chip is placed at the integer coordinate x_i. Some chips can have equal coordinates.

You can perform each of the two following types of moves any (possibly, zero) number of times on any chip:

  * Move the chip i by 2 to the left or 2 to the right for free (i.e. replace the current coordinate x_i with x_i - 2 or with x_i + 2); 
  * move the chip i by 1 to the left or 1 to the right and pay one coin for this move (i.e. replace the current coordinate x_i with x_i - 1 or with x_i + 1). 



Note that it's allowed to move chips to any integer coordinate, including negative and zero.

Your task is to find the minimum total number of coins required to move all n chips to the same coordinate (i.e. all x_i should be equal after some sequence of moves).

Input

The first line of the input contains one integer n (1 ≤ n ≤ 100) — the number of chips.

The second line of the input contains n integers x_1, x_2, ..., x_n (1 ≤ x_i ≤ 10^9), where x_i is the coordinate of the i-th chip.

Output

Print one integer — the minimum total number of coins required to move all n chips to the same coordinate.

Examples

Input


3
1 2 3


Output


1


Input


5
2 2 2 3 3


Output


2

Note

In the first example you need to move the first chip by 2 to the right and the second chip by 1 to the right or move the third chip by 2 to the left and the second chip by 1 to the left so the answer is 1.

In the second example you need to move two chips with coordinate 3 by 1 to the left so the answer is 2.
import java.io.*;
import java.math.BigInteger;
import java.util.*;


public class Main {

    private static List<List<Integer>> subsets;
    private static int count = 0;
    private static BigInteger thirteen = new BigInteger("13");
    private static BigInteger five = new BigInteger("5");
    public static void main(String[] args) throws IOException {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        InputReader.OutputWriter out = new InputReader.OutputWriter(outputStream);
        Scanner scanner = new Scanner(System.in);


        int n = in.nextInt();
        int [] a = new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = in.nextInt();
        }
        for (int i = 0; i < a.length; i++) {
            if(a[i]%2==0) a[i] = 0;
            else a[i] = 1;
        }
        long min = Long.MAX_VALUE;
        for (int i = 0; i < a.length; i++) {
            long ans = 0;
            for (int j = 0; j < a.length; j++) {
                if(i!=j) {
                    if(Math.abs(a[j]-a[i])%2!=0) {
                        ans+=Math.abs(a[j]-a[i]);
                    }
                }
            }
            min = Math.min(min,ans);
        }
        out.println(min);


        out.flush();
    }
    private static int lowerBound(String [] a, char letter) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo<=hi) {
            int med = lo + (hi-lo)/2;
            if(letter <= a[med].charAt(0)) {
                hi = med - 1;
            }
            else {
                lo = med + 1;
            }
        }
        if(lo < 0 || lo >= a.length) return  -1;
        return a[lo].charAt(0) == letter ? lo : -1;
    }
    private static int upperBound(String [] a, char letter) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo<=hi) {
            int med = lo + (hi-lo)/2;
            if(letter >= a[med].charAt(0)) {
                lo = med + 1;
            }
            else {
                hi = med - 1;
            }
        }
        return hi;
    }
    static List<Integer> del (int n) {
        List<Integer> list = new ArrayList<>();
        for (int i=1;i*i<=n;i++) {
            if(n%i==0) {
                list.add(i);
                if(i*i!=n) {
                    list.add(n/i);
                }
            }
        }
        return list;
    }
    static int sumOfNumbers(int n) {
        int sum = 0;
        while (n>0) {
            sum+=n%10;
            n/=10;
        }
        return sum;
    }
    static long binPow(long a, long b, long m) {
        //a %= m;
        long res = 1;
        while (b > 0) {
            if (b%2!=0) {
               res = res * a % m;
            }
            a = a * a % m;
            b >>= 1;
        }
        return res;
    }

    static boolean isPrime(long n) {
        if(n < 2) return false;
        for(long i = 2;i*i<=n;i++) {
            if(n%i==0) return false;
        }
        return true;
    }
    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b,a%b);
    }
    public boolean isPowerOfFour(int num) {
        int n = Integer.bitCount(num);
        String s = Integer.toBinaryString(num);
        if(n == 1 && s.length()%2!=0) return true;
        return false;
    }
    static boolean isAscending(int [] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if(a[i+1] < a[i]) return false;
        }
        return true;
    }
    static boolean isDescending(int [] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if(a[i+1] > a[i]) return false;
        }
        return true;
    }
    static void reverseArray(int [] a) {
        int i = 0;
        int j = a.length - 1;
        while (i<=j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }
    static boolean isPossible(int [] a, int [] b) {
        for (int i = 0; i < 26; i++) {
            if(a[i] == 0  && b[i]!=0) return false;
        }
        return true;
    }
    private static int [] freq(String s) {
        int [] f = new int[26];
        for (char c : s.toCharArray()) {
            f[c-'a']++;
        }
        return f;
    }
    private static void dfs(HashMap<Integer,List<Integer>> map, HashMap<Integer,Long> values, int x, int v,HashSet<Integer> set) {
        if(!set.contains(x)) {
            values.put(x, values.getOrDefault(x, 0L) + v);
            set.add(x);
        }
        if(!map.containsKey(x)) {
            return;
        }
        List<Integer> list = map.get(x);
        for (int i = 0; i < list.size(); i++) {
            int key = list.get(i);
            if(!set.contains(key)) {
                values.put(key,values.get(key) +  v);
                set.add(key);
            }
        }
        for (int i = 0; i < list.size();i++) {
            int key = list.get(i);
            dfs(map,values,key,v,set);
        }
    }

    static double gcd(double a,double b) {
        return b == 0 ? a : gcd(b,a%b);
    }
}
class Point {
    int id;
    int value;

    public Point(int id, int value) {
        this.id = id;
        this.value = value;
    }
}

class InputReader extends BufferedReader {
    StringTokenizer tokenizer;

    public InputReader(InputStream inputStream) {
        super(new InputStreamReader(inputStream), 32768);
    }

    public InputReader(String filename) {
        super(new InputStreamReader(Thread.currentThread().getContextClassLoader().getResourceAsStream(filename)));
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(readLine());
            } catch (IOException e) {
                throw new RuntimeException();
            }
        }
        return tokenizer.nextToken();
    }
    public Integer nextInt() {return Integer.valueOf(next());}
    public Long nextLong() {return  Long.valueOf(next());}
    public Double nextDouble() {return Double.valueOf(next());}

    static class OutputWriter extends PrintWriter {
        public OutputWriter(OutputStream outputStream) {
            super(outputStream);
        }

        public OutputWriter(Writer writer) {
            super(writer);
        }

        public OutputWriter(String filename) throws FileNotFoundException {
            super(filename);
        }

        public void close() {
            super.close();
        }
    }
}