English · Original
Chinese · Translation
Formal · Original
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]$, we can permute it so that it becomes $[20, 40, 10, 30]$. Then on the first and the second positions the integers became larger ($20>10$, $40>20$) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals $2$. 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 $n$ ($1 \leq n \leq 10^5$) — the length of the array.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — 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.
[samples]
## Note
In the first sample, one of the best permutations is $[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.
你被给定一个整数数组。Vasya 可以对其中的整数进行排列（改变顺序）。他希望这样做，使得尽可能多的整数出现在原本较小整数所在的位置。请帮助 Vasya 找到满足这一条件的最大整数个数。
例如，给定数组 $[ 10, 20, 30, 40 ]$，我们可以将其排列为 $[ 20, 40, 10, 30 ]$。此时，在第一和第二个位置，整数变大了（$20 > 10$，$40 > 20$），而在第三和第四个位置没有变大，因此该排列中 Vasya 想要最大化的目标值为 $2$。请参阅第一个示例的注释，那里还有一个演示用例。
请帮助 Vasya 对整数进行排列，使得新数组中比原数组对应位置元素更大的元素个数最大化。
第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 数组的长度。
第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 10^9$) —— 数组的元素。
请输出一个整数 —— 在排列后，有多少个数组元素出现在原本有更小元素的位置上，且该数量最大。
在第一个样例中，一个最优排列是 $[ 1, 5, 5, 3, 10, 1, 1 ]$。从第二个位置到第五个位置，元素都变大了，因此该排列的答案为 4。
在第二个样例中，无法通过任何排列使任一元素变大，因此答案为 0。
## Input
第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$) —— 数组的长度。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($1 lt.eq a_i lt.eq 10^9$) —— 数组的元素。
## Output
请输出一个整数 —— 在排列后，有多少个数组元素出现在原本有更小元素的位置上，且该数量最大。
[samples]
## Note
在第一个样例中，一个最优排列是 $[ 1, 5, 5, 3, 10, 1, 1 ]$。从第二个位置到第五个位置，元素都变大了，因此该排列的答案为 4。在第二个样例中，无法通过任何排列使任一元素变大，因此答案为 0。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the array.
Let $ A = (a_1, a_2, \dots, a_n) $ be the original array of integers.
Let $ B = (b_1, b_2, \dots, b_n) $ be a permutation of $ A $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
3. $ B $ is a permutation of $ A $, i.e., $ B \in \text{Perm}(A) $
**Objective**
Maximize the number of indices $ i \in \{1, \dots, n\} $ such that $ b_i > a_i $.
That is, compute:
$$
\max_{B \in \text{Perm}(A)} \left| \left\{ i \in \{1, \dots, n\} \mid b_i > a_i \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "C. Reorder the Array",
"description": {
"content": "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. ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1008C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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. ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个整数数组。Vasya 可以对其中的整数进行排列（改变顺序）。他希望这样做，使得尽可能多的整数出现在原本较小整数所在的位置。请帮助 Vasya 找到满足这一条件的最大整数个数。\n\n例如，给定数组 $[ 10, 20, 30, 40 ]$，我们可以将其排列为 $[ 20, 40, 10, 30 ]$。此时，在第一和第二个位置，整数变大了（$20 > 10$，$40 > 20$），而在第三和...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the original array of integers. \nLet $ B = (b_1, b_2, \\dots, b_n) $ be a permutation o...",
"is_translate": false,
"language": "Formal"
}
]
}