B. Beautiful Paintings-白红宇

B. Beautiful Paintings

阅读量：5273 次

发布时间：2019-06-14

本文共 1595 字，大约阅读时间需要 5 分钟。

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 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₁, a₂, ..., 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

Input

4 200 100 100 200

Output

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.

思维，考虑一个没有重复的几个数，结果是n-1，那么如果有重复的数，就先不管重复的数各取一个组成一个序列，再把剩下的各取一个组成一个序列，能够组成m个序列，m是重复数字最多的个数，结果就是n-m.

#include 
     
      #include 
      
       #include 
       using namespace std;int main(){    int n,m=1,d;    map
        
         p;    cin>>n;    for(int i=0;i
         
          >d;        p[d]++;        if(p[d]>m)m=p[d];    }    cout<

转载于:https://www.cnblogs.com/8023spz/p/7497443.html

你可能感兴趣的文章