651B.md (1460B)
1 Source: https://codeforces.com/problemset/problem/651/B 2 3 B. Beautiful Paintings 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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*. 24 25 Input 26 27 The first line of the input contains integer *n* (1 ≤ *n* ≤ 1000) — the number of painting. 28 29 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. 30 31 Output 32 33 Print one integer — the maximum possible number of neighbouring pairs, such that *a**i* + 1 > *a**i*, after the optimal rearrangement. 34 35 Examples 36 37 Input 38 39 ``` 40 5 41 20 30 10 50 40 42 ``` 43 44 Output 45 46 ``` 47 4 48 ``` 49 50 Input 51 52 ``` 53 4 54 200 100 100 200 55 ``` 56 57 Output 58 59 ``` 60 2 61 ``` 62 63 Note 64 65 In the first sample, the optimal order is: 10, 20, 30, 40, 50. 66 67 In the second sample, the optimal order is: 100, 200, 100, 200.