You are given an array of integers. Vasya can permute (change order) its integers. He wants to do it so that as many as possible integers will become on a place where a smaller integer used to stand. Help Vasya find the maximal number of such integers.

For instance, if we are given an array $[10, 20, 30, 40]$, we can permute it so that it becomes $[20, 40, 10, 30]$. Then on the first and the second positions the integers became larger ($20>10$, $40>20$) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals $2$. Read the note for the first example, there is one more demonstrative test case.

Help Vasya to permute integers in such way that the number of positions in a new array, where integers are greater than in the original one, is maximal.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array.


-----Output-----

Print a single integer — the maximal number of the array's elements which after a permutation will stand on the position where a smaller element stood in the initial array.


-----Examples-----
Input
7
10 1 1 1 5 5 3

Output
4

Input
5
1 1 1 1 1

Output
0



-----Note-----

In the first sample, one of the best permutations is $[1, 5, 5, 3, 10, 1, 1]$. On the positions from second to fifth the elements became larger, so the answer for this permutation is 4.

In the second sample, there is no way to increase any element with a permutation, so the answer is 0.

Difficulty: competition

Starter code:

Solutions:
from collections import Counter

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

res = 0
cur = 0
for i in sorted(c.keys()):
  d = min(c[i], cur)
  cur -= d
  res += d
  cur += c[i]

print(res)

3

def solve(N, A):
    A.sort()

    i = 0
    j = 0
    c = 0

    while j < N:
        while j < N and A[j] == A[i]:
            j += 1

        if j == N:
            break

        c += 1
        i += 1
        j += 1

    return c


def main():
    N = int(input())
    A = [int(e) for e in input().split(' ')]
    print(solve(N, A))


def __starting_point():
    main()

__starting_point()

n = int(input())
arr = [int(t) for t in input().split()]
arr.sort()

nx = 0
i = 0
res = 0
while i < n:
    j = i
    while j < n and arr[i] == arr[j]:
        j += 1
    nx = max(nx, j)
    t = min(j - i, n - nx)
    nx += t
    nx = min(nx, n)
    res += t
    i = j
print(res)


from collections import *
print(int(input()) - max(Counter(map(int,input().split())).values()))

n = int(input())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
r = 0
s = 0
m = 1
for i in range(1, n):
    if arr[i] < arr[i - 1]:
        s += m
        m = 1
    else:
        m += 1
    if s:
        s -= 1
        r += 1
print(r)


from collections import Counter


def main():
    input()
    cnt = Counter(list(map(int, input().split())))
    a, *rest = sorted(cnt.keys())
    pool, res = cnt[a], 0
    for a in rest:
        c = cnt[a]
        if pool < c:
            res += pool
            pool = c
        else:
            res += c
    print(res)


def __starting_point():
    main()

__starting_point()


def main():
	n=int(input())
	li=list(map(int,input().split()))
	li.sort()
	li.reverse()
	i,j,count=0,1,0
	while j<len(li):
		if li[j]<li[i]:
			j+=1
			i+=1
			count+=1
		else:
			j+=1
	print(count)
	

def __starting_point():
	main()

__starting_point()

def readints():
    return [int(x) for x in input().strip().split()]


def main():
    n = readints()[0]
    a = sorted(readints())

    marker = 0
    for i in range(n):
        if a[i] > a[0]:
            break
        marker += 1

    ans = 0
    for i in range(n):
        while marker < n:
            if a[i] < a[marker]:
                ans += 1
                marker += 1
                break
            marker += 1

    print(ans)


def __starting_point():
    main()

__starting_point()

n = int(input())

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

z = {}

for i in range(n):
    if a[i] not in z:
        z[a[i]] = 1
    else:
        z[a[i]] +=1

ans = n


s = sorted(z.values())

ans = ans - max(s)

print(ans)


n = int(input())
a = [int(i) for i in input().split()]
d = {}
for i in a:
    d[i] = 0

for i in a:
    d[i] += 1

ans = n - max(d.values())
print(ans)


def solution(n, num_array):

	# If there is only one element in the list, return 0.
	if (len(num_array) == 1):
		return 0
	

	# sort the array first
	num_array.sort()
	idx1 = 0
	idx2 = 1
	res = 0
	while (idx2 < len(num_array)):
		num1 = num_array[idx1]
		num2 = num_array[idx2]

		if (num1 < num2):
			res += 1
			idx1 += 1

		idx2 += 1

	
	return res




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

print(solution(n, num_array))




def solution(n, num_array):

	# If there is only one element in the list, return 0.
	# import pdb; pdb.set_trace
	if (len(num_array) == 1):
		return 0
	

	# sort the array first
	num_array.sort()
	idx1 = 0
	idx2 = 1
	res = 0
	while (idx2 < len(num_array)):
		num1 = num_array[idx1]
		num2 = num_array[idx2]

		if (num1 < num2):
			# swap the numbers
			res += 1
			idx1 += 1
			idx2 += 1

		else:
			idx2 += 1

	# print(sorted_arr)
	return res




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

print(solution(n, num_array))




n = int(input())
arr = sorted([int(a) for a in input().split()])
j = 0
for i in range(0, n):
    if arr[i] > arr[j]:
        j += 1
print(j)



n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
d = 0
j = 0
m = 1
for i in range(1, len(a)):
    if a[i] == a[j]:
        m += 1
    else:
        if m > d:
            d = m
        m = 1
        j = i

if m > d:
    d = m

print(len(a) - d)


def count_sort(mass, st):
    i = st
    while i < len(mass):
        if mass[i] != mass[st]:
            break
        i += 1
    return i - st


n = int(input())

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

a.sort()

i = a.count(a[0]) 
left = i
res = n - left
while i < len(a) :
    count = count_sort(a, i)
    i += count
    left -= count
    if left < 0:
        res += left
        left = 0
    left += count
    
print(res)


def go():
    n = int(input())
    a = sorted([int(i) for i in input().split(' ')])
    total = i = j = 0
    while j < n:
        if a[i] == a[j]:
            j += 1
        else:
            break
    while j < n:
        if a[i] < a[j]:
            total += 1
            i += 1
        j += 1
    return total

print(go())


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

a.sort()

i = 0
for j in range(n):
	if a[i] < a[j]:
		i = i + 1

print(i)

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


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

from collections import Counter as co
x=int(input())
y=list(map(int,input().split()))
print(x-max(co(y).values()))


from collections import*
n = int(input())

s = list(map(int, input().split()))

x = max(Counter(s).values())

print(n - x)



from collections import Counter
length = int(input())
array = list(map(int, input().split()))
dic = Counter(array)
value_list = list(dic.values())
print(len(array) - max(value_list))

from collections import *

print( int(input()) - max(Counter(map(int, input().split())).values()) )

from collections import*
print(int(input())-max(Counter(map(int,input().split())).values()))