首页 > > 程序设计 > C/C++ >

A. Reorder the Array

2018-08-26 17:16:46来源：博客园阅读 ()

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]$

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$

The second line contains $n$

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

input

Copy

5
1 1 1 1 1

output

Copy

Note

In the first sample, one of the best permutations is $[1, 5, 5, 3, 10, 1, 1]$

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

给你一个序列，你可以生成这个序列的任意一个排列，对于某个排列，

如果这个排列上某个位置的值大于原序列的值，那么就会产生1的贡献，问你最大能有多少贡献。

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<string.h>
 5 #include<map>
 6 using namespace std;
 7 const int maxn = int(1e5) + 7;
 8 int a[maxn], n, r = 1, ans;
 9 int main()
10 {
11     cin >> n;
12     for (int i = 1; i <= n; i++)
13         cin >> a[i];
14     sort(a+ 1, a+ 1 + n);
15     for (int i = 1; i <= n; i++)
16     {
17         while (r <= n && a[r] <= a[i])
18             r++;
19         if (r <= n)
20             ans++, r++;
21     }
22     cout << ans << std::endl;
23     return 0;
24 }