There are n pictures delivered for the new exhibition. The i-th painting has beauty a_{i}. We know that a visitor becomes happy every time he passes from a painting to a more beautiful one.

We are allowed to arranged pictures in any order. What is the maximum possible number of times the visitor may become happy while passing all pictures from first to last? In other words, we are allowed to rearrange elements of a in any order. What is the maximum possible number of indices i (1 ≤ i ≤ n - 1), such that a_{i} + 1 > a_{i}.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 1000) — the number of painting.

The second line contains the sequence a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000), where a_{i} means the beauty of the i-th painting.


-----Output-----

Print one integer — the maximum possible number of neighbouring pairs, such that a_{i} + 1 > a_{i}, after the optimal rearrangement.


-----Examples-----
Input
5
20 30 10 50 40

Output
4

Input
4
200 100 100 200

Output
2



-----Note-----

In the first sample, the optimal order is: 10, 20, 30, 40, 50.

In the second sample, the optimal order is: 100, 200, 100, 200.

Difficulty: interview

Starter code:

Solutions:
from collections import defaultdict
n = int(input())
A = [int(x) for x in input().split()]
D = defaultdict(int)
for a in A: D[a] += 1
S = set(D.keys())
ans = len(S) - 1
while S:
    for k in D:
        D[k] -= 1
        if D[k] <= 0 and k in S:
            S.remove(k)
    ans += len(S) - 1
print(ans + 1)


def seq(a, new):
    nonlocal count
    for i in range(1, len(a)):
        if a[i] == a[i - 1]:
            new.append(a[i])
    if len(a) > 1:
        count += len(a) - len(new) - 1
    if len(new) == 0:
        return
    else:
        a = new[:]
        new = []
        seq(a, new)

n = int(input())
a = list(map(int, input().split()))
a.sort()
new = []
count = 0
seq(a, new)
print(count)

    
    


#! /usr/bin/env python3

def main():
    input()
    nums = map(int, input().split())

    nums = sorted(nums)
    length = len(nums)
    count = 0
    last_num = nums[0]
    for i in range(length):
        if nums[i] is None:
            continue
        last_num = nums[i]
        for j in range(i + 1, length):
            if nums[j] is None:
                continue
            if nums[j] > last_num:
                count += 1
                last_num = nums[j]
                nums[j] = None

    print(count)


main()

#!/usr/bin/env python3

N = int(input())
A = list(map(int, input().split()))

A = sorted(A)
A = [(a, True) for a in A]

happiness = 0
uses_left = N

while True:
	last_a = None
	for i in range(len(A)):
		a, usable = A[i]
		if not usable: continue
		if last_a is None:
			last_a = a
			A[i] = (a, False)
			uses_left -= 1
			continue
		if last_a < a:
			happiness += 1
			A[i] = (a, False)
			uses_left -= 1
			last_a = a
			continue
	if uses_left == 0: break

print(happiness)

from collections import *
ans=0
c=Counter()
n=int(input())
for x in input().split(): c[int(x)]+=1
while len(c)>1:
    ans+=len(c)-1
    for x in set(c): 
        c[x]-=1
        if c[x]==0: del c[x]
print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort()
for i in range(n):
    A[i] = [A[i], 0]
answer = 0
per2 = -float('infinity')
per = 0
for i in range(n-1):
    if A[i][1] == 0:
        A[i][1] = 1
        per = A[i][0]
        for j in range(i+1, n):
            if A[j][1] == 0:
                if A[j][0] > per:
                    per = A[j][0]
                    A[j][1] = 1
                    answer+=1
print(answer)
                    
    


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

c = [0] * 1001
for ai in a:
    c[ai] += 1
ans = 0
for t in range(max(c)):
    was = False
    for i in range(1, 1001):
        if c[i] > 0:
            if was:
                ans += 1
            else:
                was = True
            c[i] -= 1
print(ans)
            


read = lambda: list(map(int, input().split()))
n = int(input())
a = list(read())
wasr = [False] * n
wasl = [False] * n
cnt = 0
inf = 10 ** 9
for i in range(n):
    if wasl[i]: continue
    wasl[i] = True
    cur = a[i]
    Min = inf
    ind = -1
    for j in range(n):
        if wasr[j]: continue
        if cur < a[j] < Min:
            Min = a[j]
            ind = j
    if ind != -1:
        wasr[ind] = True
        cnt += 1
        #print(cur, a[ind])
print(cnt)
        


n = int(input())
count = [0] * 1001
c = [0] * 1001
pictures = list(map(int, input().split()))
for i in pictures:
    count[i] += 1
res = 0
while count != c:
    res -= 1
    for i in range(len(count)):
        if count[i] > 0:
            count[i] -= 1
            res += 1
print(res)

n = int(input())
a = [int(x) for x in input().split()]
b = {}
for x in a:
    if x in b:
        b[x] += 1
    else:
        b[x] = 1
summa = 0
while len(b) > 0:
    count = 0
    c = b.copy()
    for x in b:
        c[x] -= 1
        if c[x] == 0:
            c.pop(x)
        count += 1
    b = c.copy()
    summa += (count - 1)
print(summa)


from collections import Counter


def read_input():
    N = int(input())
    A = [int(i) for i in input().strip().split()]
    return A


def solution(A):
    c = Counter(A)
    ans = 0
    stop = False
    while not stop:
        stop = True
        count = 0
        for key in c:
            if c[key]:
                count += 1
                stop = False
                c[key] -= 1
        if count:
            ans += (count - 1)
    return ans


def __starting_point():
    A = read_input()
    print(solution(A))

__starting_point()

import functools
import math
import sys

n = int(input())
a = list(map(int, input().split()))
ans = 0
a.sort()
while len(a) > 1:
    t = []
    for i in range(1, len(a)):
        if a[i] > a[i - 1]:
            ans += 1
        else:
            t.append(a[i])
            #temp += 1
    a = t
print(ans)

from collections import Counter
input()
a = map(int, input().split())
b = Counter(a)
b = list(b.values())
print(sum(b) - max(b))

n = int(input())
pictures = list(map(int, input().split()))
d = dict()
for i in pictures:
    d[i] = 0
for i in pictures:
    d[i] += 1
a = sorted(d.values())
i = 1
r = 0
l = len(a) - 1
s = 0
while i < len(a):
    c = i
    while (i < len(a)) and (a[i] == a[i - 1]):
        i += 1
    s += l * (a[i - 1] - r)
    l -= (i - c + 1)
    r = a[i - 1]
    i += 1
print(s)

n=int(input().strip())
d={}
ans=0
for i in input().strip().split():
	if i in d:
		d[i]=d[i]+1
	else:
		d[i]=1
while d:
	l=list(d.keys())
	for i in l:
		if d[i]==1:
			del d[i]
		else:
			d[i]=d[i]-1
	ans=ans+len(l)-1
print(ans)

n=int(input())
x=[int(z) for z in input().split()]
x.sort()
y=[]
cur=x[0]
curs=1
i=1
y=[]
while i<n:
    r=x[i]
    if r==cur:
        curs+=1
    else:
        d=[cur]*curs
        y+=[d]
        curs=1
        cur=r
    i+=1
y+=[[cur]*curs]
res=0

while len(y)>1:
    u=[]
    for h in y:
        h.pop()
        if h!=[]:
            u+=[h]
    res+=len(y)-1
    y=u[:]
print(res)
        


def __starting_point():
    n = int(input())
    lst = list(map(int,input().split(' ')))
    lst.sort()
    h,i = 0,0
    trav = []
    while i<n-1:
        if i in trav:
            i+=1
            continue
        j = i+1
        s = lst[i]
        while j<n:
            #print(j,trav)
            if lst[j]>s  and j not in trav:
                h+=1
                s=lst[j]
                trav.append(j)
            j+=1
        trav.append(i)
        i+=1  
    print(h)
        
        
        
            
        


    

__starting_point()

# ATTENTION:
# never attend codeforces if u're drunk
n = int(input())
a = sorted([int(x) for x in input().split()])
c = dict()
for x in a: c[x] = c[x]+1 if x in c else 1
uniq = sorted(c.keys())
C=0
while n>0:
    t = 0
    for u in uniq:
        if c[u] == 0:
            continue
        c[u] -= 1
        n -= 1
        t += 1
    C += t-1
print(C)


size = 1001
n = int(input())
a = [0] * size
ans = 0
num = map(int, input().split())
for b in num:
    a[b] += 1
    
while a.count(0) != size:
    cnt = 0
    for i in range(size):
        if a[i]:
            cnt += 1
            a[i] -= 1
    ans += cnt - 1

print(ans)

def __starting_point():
    n = int(input())
    lst = list(map(int,input().split(' ')))
    lst.sort()
    h,i = 0,0
    trav = []       #tracks travelled
    while i<n-1:
        if i in trav:
            i+=1
            continue
        j = i+1
        s = lst[i]
        while j<n:
            #print(j,trav)
            if lst[j]>s  and j not in trav:
                h+=1
                s=lst[j]
                trav.append(j)
            j+=1
        trav.append(i)
        i+=1  
    print(h)
'''
B. Beautiful Paintings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are n pictures delivered for the new exhibition. The i-th painting has beauty ai. We know that a visitor becomes happy every time he passes from a painting to a more beautiful one.

We are allowed to arranged pictures in any order. What is the maximum possible number of times the visitor may become happy while passing all pictures from first to last? In other words, we are allowed to rearrange elements of a in any order. What is the maximum possible number of indices i (1 ≤ i ≤ n - 1), such that ai + 1 > ai.
Input

The first line of the input contains integer n (1 ≤ n ≤ 1000) — the number of painting.

The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ 1000), where ai means the beauty of the i-th painting.
Output

Print one integer — the maximum possible number of neighbouring pairs, such that ai + 1 > ai, after the optimal rearrangement.
Examples
Input

5
20 30 10 50 40

Output

4

Input

4
200 100 100 200

Output

2

Note

In the first sample, the optimal order is: 10, 20, 30, 40, 50.

In the second sample, the optimal order is: 100, 200, 100, 200.
'''
        
        
        
            
        


    

__starting_point()

n = int(input())
a = sorted(list(map(int,input().split())))
vis = [False for i in range(n)]
for i in range(n) :
    for j in range(i+1,n) :
        if i==j : continue
        if a[i]<a[j] and  not vis[j] :
            vis[j] = True
            break

print(sum([fact for fact in vis]))
            


n = int(input())
count = [0] * 1001
c = [0] * 1001
pictures = list(map(int, input().split()))
for i in pictures:
    count[i] += 1
res = 0
while count != c:
    res -= 1
    for i in range(len(count)):
        if count[i] > 0:
            count[i] -= 1
            res += 1
print(res)


n = int(input())
x = [0 for i in range(0, 1010)]
for i in map(int, input().split()):
    x[i] += 1
d = 0
for i in range(0, 1010):
    d = max(d, x[i])
print(n - d)

from collections import Counter
n = int(input())
print(n - Counter(list(map(int, input().split()))).most_common(1)[0][1])