C. Reorder the Array
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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][10,20,30,40], we can permute it so that it becomes [20,40,10,30][20,40,10,30]. Then on the first and the second positions the integers became larger (20>1020>10, 40>2040>20) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals 22. 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 nn (1≤n≤1051≤n≤105) — the length of the array.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — 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
Copy 
7
10 1 1 1 5 5 3
output
Copy 
4
input
Copy 
5
1 1 1 1 1
output
Copy 
0
Note

In the first sample, one of the best permutations is [1,5,5,3,10,1,1][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.

我改变后数组的各个数要比原先的数大才可以，记录这些可以改变的个数

然后发现有个规律，拿总数减去这个数组中相同数量最多的个数。

比如样例1：

7
10 1 1 1 5 5 3

最多的相同数是1 ， 它有3个------7-3 =4 ---bingo

样例2：

5
1 1 1 1 1

最多的相同数是 1 ， 它有5个 -----5-5=0----bingo

原因比如这个例子：1  1  1  3  3  3    3  3  5 5 10

                              3  3  3  5  5  10  1  1  1  3  3 

这样对应起来，1 3 （从较小的数开始 ）， 总有5（ 相同数的最大长度）这个长度不能对应

代码：

#include <stdio.h>
#include <iostream>
#include <map>
#include <bits/stdc++.h>
using namespace std;
int main()
{
	map<int , int> M;
	int n , m , max = -99999;
	scanf("%d" , &n);
	for(int i = 0 ; i < n ; i++)
	{
		scanf("%d" , &m);
		M[m]+=1;
		if(M[m] > max)
		{
			max = M[m]; 
		}
	}
	printf("%d\n" , n-max);
	return 0;
}