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.
'''a=[int(i) for i in input().split()]
x=a[0]
y=a[1]
z=a[2]
if y==x and z==0:
    print('0')
elif x>y+z:
    print('+')
elif y>x+z:
    print('-')
else:
    print('?')
n=int(input())
z=[int(i) for i in input().split()]
x=[]
d=0
v=''
for i in range(n):
    c=0
    e=0
    for f in range(len(z)):
        if z[f]>c and f+1 not in x:
            c=z[f]
            e=f+1
    d+=(i*c)+1
    x.append(e)
print(d)
for i in x:
    v+=str(i)
    v+=' '
print(v)

f=int(input())
g=[int(i) for i in input().split()]
for i in range(len(g)-1):
    for f in range(len(g)-1-i):
        if g[f]>g[f+1]:
            g[f],g[f+1]=g[f+1],g[f]
if g[0]*g[1]>g[-2]*g[-3] and g[-1]>0:
    print(g[-1]*g[0]*g[1])
else:
    print(g[-1]*g[-2]*g[-3])
for u in range(int(input())):
    z=int(input())
    y=[int(f) for f in input().split()]
    y.sort()
    d=0
    for i in y:
        d+=i
    if d<2048:
        print('No')
        continue
    if 2048 in y:
        print('yes')
        continue
    for x in range(z+1):
        if 2048 in y:
            print('yes')
            break
        for i in range(len(y)-1):
            if y[i]==y[i+1]:
                y[i+1]=y[i]*2
                y.pop(i)
            if i>len(y)-3:
                break
        y.sort()
    else:
        print('no')
n=int(input())
x=[]
for i in range(1,((n**2)//2)+1):
    x.append(n**2+1-i)
    x.append(i)
    if len(x)==n:
        print(*x)
        x=[]
for z in range(int(input())):
    z=int(input())
    x=[int(i) for i in input().split()]
    f=0
    o=0
    t=0
    for i in range(z):
        if x[i]%3==0:
            f+=1
        elif x[i]%3==1:
            o+=1
        else:
            t+=1
    if o<t:
        print(f+o+(t-o)//3)
    else:
        print(f+t+(o-t)//3)
n=int(input())
if n%2==1:
    print(0)
elif n%4==0:
    print((n//4)-1)
else:
    print(n//4)
n=[int(i) for i in input().split()]
if n[2]>=0 and n[0]>n[1]:
    print('NO')
elif n[2]<=0 and n[0]<n[1]:
    print('NO')
elif n[2]==0:
    if n[0]==n[1]:
        print('YES')
    else:
        print('NO')
elif (n[1]-n[0])%n[2]==0:
    print('YES')
else:
    print('NO')
for f in range(int(input())):
    f=[int(i) for i in input().split()]
    a=f[0]
    b=f[1]
    c=f[2]
    r=f[3]
    a,b=min(a,b),max(a,b)
    if c+r<=a or c-r>=b:
        print(b-a)
    elif c<=a:
        print(max(b-c-r,0))
    elif c>=b:
        print(max(c-a-r,0))
    else:
        v=max(b-c-r,0)
        print(v+max(c-a-r,0))
def bt(p,c):
    if c%p+c//p==0:
        return ''
    else:
        return bt(p,c//p)+str(c%p)
print(bt(int(input()),int(input())))
for t in range(int(input())):
    t=[int(i) for i in input().split()]
    n=t[0]
    m=t[1]
    x=t[2]
    y=t[3]
    d=0
    for f in range(n):
        e=input()
        c=0
        for i in range(m):
            if c==0 and i==m-1:
               if e[i]=='.':
                   d+=x
               break
            elif c==1:
                c=0
                continue
            else:
                if e[i]=='.' and e[i+1]=='.' and y<2*x:
                    c=1
                    d+=y
                elif e[i]=='.':
                    d+=x
                else:
                    continue
    print(d)
x=[int(i) for i in input().split()]
d=x[3]
x.pop(3)
x.sort()
a=x[0]
b=x[1]
c=x[2]
print(max(d-b+a,0)+max(d+b-c,0))
d=int(input())
s=input()
x=s.count('0')
y=s.count('1')
if y!=x:
    print(1)
    print(s)
else:
    print(2)
    print(s[0:-1],s[-1],sep=' ')
from random import choice
def qs(y):
    if len(y)<2:
        return y
    d=choice(y)
    s=[]
    e=[]
    l=[]
    for i in y:
        if i<d:
            s.append(i)
        elif i>d:
            l.append(i)
        else:
            e.append(i)
    return qs(l)+e+qs(s)
n=int(input())
m=int(input())
a=[]
d=0
for i in range(n):
    a.append(int(input()))
c=qs(a)
for i in range(n):
    d+=c[i]
    if d>=m:
        print(i+1)
        break
n=int(input())
if n%2==0:
    print((n**2)//2)
else:
    print(((n**2)//2)+1)
for f in range(n):
    c=''
    for i in range(n):
        if f%2==0:
            if i%2==0:
                c+='C'
            else:
                c+='.'
        else:
            if i%2==1:
                c+='C'
            else:
                c+='.'
    print(c)
n=int(input())
c=''
for i in range(1,n+1):
    c+=str(i)
print(c[n-1])
c=[int(i) for i in input().split()]
d=[int(i) for i in input().split()]
e=[int(i) for i in input().split()]
y=0
x=0
for i in d:
    if i%2==0:
        x+=1
for i in e:
    if i%2==0:
        y+=1
f=c[0]-x
g=c[1]-y
print(min(x,g)+min(y,f))
for i in range(int(input())):
    n=int(input())
    a=[int(i) for i in input().split()]
    a.sort()
    c=a[0]*a[-1]
    for i in range(0,4*n,2):
        if a[i]!=a[i+1]:
            print('NO')
            break
        elif a[i]*a[4*n-i-1]!=c:
            print('NO')
            break
    else:
        print('YES')
c=[int(i) for i in input().split()]
n=c[0]
m=c[1]
a=c[2]
b=c[3]
if b/m>=a:
    print(n*a)
elif (n%m)*a<b:
    print((n//m)*b+(n%m)*a)
else:
    print(((n//m)+1)*b)
a=input().split()
n=int(a[0])
l=int(a[1])
c=[int(i) for i in input().split()]
for i in range(n):
    for f in range(n-i-1):
        if c[f]>c[f+1]:
            c[f],c[f+1]=c[f+1],c[f]
d=0
for i in range(n-1):
    if (c[i+1]-c[i])/2>d:
        d=(c[i+1]-c[i])/2
if d<max(c[0],l-c[-1]):
    d=max(c[0],l-c[-1])
print(d)
d=input().split()
s=int(d[0])
n=int(d[1])
v=[]
for i in range(n):
    v.append([int(i) for i in input().split()])
for i in range(n):
    for f in range(n-i-1):
        if v[f][0]>v[f+1][0]:
            v[f],v[f+1]=v[f+1],v[f]
for i in v:
    if i[0]>=s:
        print('NO')
        break
    else:
        s+=i[1]
else:
    print('YES')
a=int(input())
c={}
for i in range(a):
    i=input()
    if i in c:
        c[i]+=1
        v=i+str(c[i])
        print(v)
    else:
        c[i]=0
        print('OK')'''
from math import sqrt
from random import randint
def ip(n):
    if n==1:
        return False
    for i in range(2,int(sqrt(n))+1):
        if n%i==0:
            return False
    return True
'''n=int(input())
v=[randint(1,n)for i in range(n)]
for i in v:
    if ip(i):
        print(i)
def s1(m,n):
    c=list(range(2,n+1))
    p=[]
    for i in range(n-1):
        if c[i]>1 and c[i]>=m:
            p.append(c[i])
            for f in range(i+1,n-1):
                if c[f]%c[i]==0:
                    c[f]=1
        elif c[i]>1:
            for f in range(i+1,n-1):
                if c[f]%c[i]==0:
                    c[f]=1
    return p'''
def s2(n):
    a=list(range(n))
    a[1]=0
    for i in a:
        if i>1:
            for j in range(i*2, len(a), i):
                a[j] = 0
    return {i**2 for i in a}
'''print(s2(1111))
def pn(n):
    c=''
    for i in range(n-1,1,-1):
        if ip(i):
            c+=str(i)
            c+=','
            break
    for i in range(n+1,100000000000000):
        if ip(i):
            c+=str(i)
            return c
print(pn(5))
v=int(input())
a=s2(v+400)
for i in range(len(a)-1):
    if a[i]<v and a[i+1]>v:
        print(a[i],a[i+1])
        break
    elif a[i]<v and a[i+1]==v:
        print(a[i],a[i+2])
        break
k=int(input())
a=s2(38000)
c=[]
for i in range(len(a)):
    if i+1 in a:
        c.append(a[i])
print(c[k-1])
c=0
a=s2(1024)
v=int(input())
d=[int(i) for i in input().split()]
d.sort()
for i in range(len(d)):
    e=0
    for j in range(len(a)):
        if d[i]%a[j]==0:
            e+=1
    if e>c:
        c=e
        v=i
print(d[v])
a=[int(i) for i in input().split()]
c=0
f=-1
for i in range(a[0],a[1]+1):
    e=0
    if ip(i):
        v=str(i)
        for j in v:
            e+=int(j)
        if e>=c:
            f=int(v)
            c=e
print(f)
a=int(input())
v=s2(1000)
for i in v:
    if a-i in v:
        c=str(i)+' '+str(a-i)
        print(c)
        break'''
'''a=int(input())
v=s2(10000)
c=0
for i in v:
    if a-i in v:
        c+=1
c//=2
if a%2==0 and a//2 in v:
    c+=1
print(c)
from math import sqrt
s=int(input())
d=[int(i) for i in input().split()]
v=s2(1000000)
for i in d:
    if i in v:
        print('YES')
    else:
        print('NO')

x=input().split()
c=int(x[0])
t=int(x[1])
e=[0]*c
for i in range(t):
    i=[int(i) for i in input().split()]
    r=0
    g=0
    for f in range(len(i)):
        if i[f]>r:
            r=i[f]
            g=f
    e[g]+=1
r=0
g=0
for f in range(len(e)):
    if e[f]>r:
        r=e[f]
        g=f
print(g+1)'''
x=int(input())
y=[(int(i))%2 for i in input().split()]
e=0
o=0
for i in y:
    if i==1:
        o+=1
    else:
        e+=1
print(min(e,o))
    
    

            
        
              
    
    






