Algorithm


A. Chips Moving
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given n chips on a number line. The i-th chip is placed at the integer coordinate xi��. 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 22 to the left or 22 to the right for free (i.e. replace the current coordinate xi�� with xi2��−2 or with xi+2��+2);
  • move the chip i by 11 to the left or 11 to the right and pay one coin for this move (i.e. replace the current coordinate xi�� with xi1��−1 or with xi+1��+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 xi�� should be equal after some sequence of moves).

Input

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

The second line of the input contains n integers x1,x2,,xn�1,�2,…,�� (1xi1091≤��≤109), where xi�� 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
Copy
3
1 2 3
output
Copy
1
input
Copy
5
2 2 2 3 3
output
Copy
2
Note

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

In the second example you need to move two chips with coordinate 33 by 11 to the left so the answer is 22.

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e2 + 1;
int n;

int main() {
#ifndef ONLINE_JUDGE
	freopen("in", "r", stdin);
#endif

	scanf("%d", &n);
	int even = 0, odd = 0;
	for(int i = 0, tmp; i < n; ++i) {
		scanf("%d", &tmp);
		if(tmp % 2 == 0) ++even;
		else ++odd;
	}

	if(even == 0 || odd == 0)
		puts("0");
	else
		printf("%d\n", min(odd, even));

	return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
1 2 3

Output

x
+
cmd
1
Advertisements

Demonstration


Codeforcess Solution A. Chips Moving-Solution in C, C++, Java, Python ,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+