AT_arc087_a [ABC082C] Good Sequence

题目描述

给定一个长度为 $N$ 的正整数序列 $a = (a_1, a_2, \ldots, a_N)$。你的目标是从 $a$ 中删除若干元素,使 $a$ 变为**好数列**。 这里,一个数列 $b$ 被称为**好数列**,当且仅当其满足以下条件: - 对于 $b$ 的每个元素 $x$,$b$ 中恰好包含 $x$ 个值为 $x$ 的元素。 例如,$(3, 3, 3)$,$(4, 2, 4, 1, 4, 2, 4)$,$()$(空数列)是好数列。而 $(3, 3, 3, 3)$、$(2, 4, 1, 4, 2)$ 不是好数列。 请计算,为了将 $a$ 变为好数列,最少需要删除的元素个数。

输入格式

输入通过标准输入给出,格式如下: > $N$ $a_1$ $a_2$ $...$ $a_N$

输出格式

输出将 $a$ 变为好数列所需删除的元素最小个数。

说明/提示

### 限制 - $1 \leq N \leq 10^5$ - $a_i$ 为整数。 - $1 \leq a_i \leq 10^9$ ### 样例解释 1 例如,将一个 $3$ 删除 $1$ 个后,$(3, 3, 3)$ 就变为好数列。 ### 样例解释 2 例如,将 $4$ 删除 $2$ 个后,$(2, 1, 2)$ 就变为好数列。 ### 样例解释 4 将 $10^9$ 删除 $1$ 个后,$()$(空数列)就是好数列。 由 ChatGPT 5 翻译