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 $ \sigma $ be a permutation of $ \{1, 2, \dots, n\} $, defining a rearranged array $ B = (a_{\sigma(1)}, a_{\sigma(2)}, \dots, a_{\sigma(n)}) $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Maximize the number of indices $ i \in \{1, \dots, n\} $ such that:
$$
a_{\sigma(i)} > a_i
$$
That is, find:
$$
\max_{\sigma \in S_n} \left| \left\{ i \in \{1, \dots, n\} \mid a_{\sigma(i)} > a_i \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "A. 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": "CF1007A"
},
"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 $ \\sigma $ be a permutation of $ \\{1, 2, \\dots, n...",
"is_translate": false,
"language": "Formal"
}
]
}