Maximum Greatness

Problem Statement

Maximum Greatness Problem Description You are given an integer array arr of length n . You may rearrange its elements in any order to form a new array rearranged_arr containing exactly the same multiset of values. The greatness of a rearrangement is the number of indices i with 0 <= i < n for which rearranged_arr[i] > arr[i] -- that is, the number of positions where the value placed after rearranging is strictly larger than the value originally at that position. Print the maximum greatness achievable over all rearrangements of arr . Input Format The first line contains a single integer n , the number of elements in arr . Each of the next n lines contains a single integer, arr[i] , for i from 0 to n - 1 . Output Format Print a single integer: the maximum possible greatness. Constraints 1 <= n <= 18000 1 <= arr[i] <= 10^9 The answer is at most n - 1 , so a 32-bit signed integer is sufficient everywhere. Examples Example 1 Input: 7 1 3 5 2 1 3 1 Output: 4 Explanation: