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 \le n \le 100$) — the number of chips.

The second line of the input contains $n$ integers $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 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$.

Difficulty: introductory

Starter code:

Solutions:
n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    A[i] %= 2
print(min(n - A.count(0), A.count(0)))

n = int(input())
a = [int(x) for x in input().split()]
c = 0
for i in a:
    c += (i % 2)
print(min(c, n - c))

n = int(input())
arr = list(map(int, input().split()))
cnt = 0
for i in range(n):
    cnt += arr[i] % 2
print(min(cnt, n - cnt))

n = int(input())
a = list(map(int, input().split()))
c = [0, 0]
for i in a:
    c[i % 2] += 1
print(min(c))

n = int(input())
a = list(map(int, input().split()))

pair = 0
impair = 0

for i in a:
    if i % 2:
        impair += 1
    else:
        pair += 1

print(min(pair, impair))

n=int(input())
l1=list(map(int,input().split()))
x=0
for item in l1:
    if item%2==0:
        x+=1
print(min(x,n-x))

n = int(input())
a = list(map(int, input().split()))
c1 = 0
c2 = 0
for i in range(n):
    if a[i] % 2 == 0:
        c1 += 1
    else:
        c2 += 1
print(min(c1, c2))


import math
tst = int(input())
a = list(map(int, input().split()))
x = 0
y = 0
for c in a:
    if c % 2 == 0:
        x += 1
    else:
        y += 1
print(min(x, y))


n = int(input())
a, b = 0, 0
for x in input().split():
    if int(x) % 2 == 0:
        a += 1
    else:
        b += 1

print(min(a, b))

def mi():
        return list(map(int, input().split()))
'''

'''
n = int(input())
a = list(mi())
for i in range(n):
    a[i] = a[i]%2
o = a.count(1)
z = n-o
print(min(o,z))


n = int(input())

x = [int(i) for i in input().split()]

odd = 0
even = 0

for i in x:
    if i % 2 == 0: even += 1
    else: odd += 1
        
print(min([odd, even]))

n = int(input())
odd = sum(e & 1 for e in map(int, input().split()))
print(min(odd, n - odd))

n = int(input())
a = list(map(int, input().split()))
ans_1 = 0
ans_2 = 0
for i in range(n):
	if a[i] % 2 == 0:
		ans_1 += 1
	else:
		ans_2 += 1

print(min(ans_1, ans_2))


n=int(input())
l=list(map(int,input().split()))
j=k=0
for i in l:
    if(i%2==1):
        j+=1
    else:
        k+=1
print(min(j,k))

# cook your dish here
n=int(input())
it=list(map(int,input().split()))
a=len([i for i in it if i%2==0])
b=n-a
if a>=b:
    print(b)
else:
    print(a)

n = int(input())
a = list(map(int, input().split()))
x = len([q for q in a if q % 2 == 0])
print(min(x, n-x))


n = int(input())
a = list(map(int, input().split()))

odd = 0
even = 0

for i in a:
    if i % 2 == 0:
        even += 1
    else:
        odd += 1

if even > odd:
    print(odd)
else:
    print(even)

def inp(): return int(input())
def ln(): return [int(x) for x in input().split()]

n = inp()
x = ln()

mn = 10**20
for i in range(n):
    # here
    cst = 0
    for c in x:
        cst += 1 if abs(c-x[i]) % 2  == 1 else 0
    mn = min(mn, cst)
print(mn)


n = int(input())
a = list(map(int, input().split()))

ch = 0
nch = 0

for i in range(n):
    if a[i] % 2 == 0:
        ch += 1
    else:
        nch += 1

print(min(ch, nch))

n=int(input())
a=list(map(int,input().split()))
s=0
s1=0
for i in range(n):
    if a[i]%2==0:
        s+=1
    else:
        s1+=1
print(min(s,s1))

MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

n, = I()
l = I()
ans = MOD
for i in range(n):
	x = l[i]
	c = 0
	for i in l:
		c += abs(x-i)%2
	ans = min(ans, c)
print(ans)

'''input
5
2 2 2 3 3

'''
import sys
from collections import defaultdict as dd
from itertools import  permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
from  heapq import heappush as hpush
from heapq import heappop as hpop
mod=10**9+7

def ri(flag=0):
	if flag==0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())


n = ri(1)

a = ri()

odd = sum([i%2 for i in a])
even = n-odd

print(min(even,odd))


n=int(input())
l=list(map(int,input().split()))
e=0
o=0
for i in l:
	if i%2==0:
		e+=1
	else:
		o+=1
print (min(e,o))