当前没有测试数据。

本题暂未上传测试数据，目前仅供阅读与练习。

本站练习请使用标准输入/输出；原卷中的文件名仅作原始资料参考。

题目描述

小 Q 有 $n$ 张怪兽卡牌，第 $i$ 只怪兽的攻击力和防御力均为 $r_i$。

每回合选择两只不同且尚未退出游戏的怪兽 $i,j$，让 $i$ 攻击 $j$。若 $i$ 的攻击力不大于 $j$ 的防御力，则无事发生；否则 $j$ 退出游戏。一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽均已发起过攻击时，游戏结束。

求通过安排攻击顺序，能够使游戏结束时未退出游戏的怪兽数量的最小值。

输入格式

第一行一个正整数 $n$，表示卡牌数。第二行 $n$ 个正整数 $r_1,\ldots,r_n$。

输出格式

输出一个整数，表示最少剩余怪兽数。

样例 1

输入

5
1 2 3 1 2

输出

2

样例 2

输入

10
136 136 136 2417 136 136 2417 136 136 136

输出

8

数据范围

$1\le n\le10^5$，$1\le r_i\le10^5$。

原卷完整题面

以下保留原卷的图示、完整样例解释、分档约束和特殊性质，便于核对。原卷中引用的外部样例文件未随本次题面上传。

下载原卷题面 PDF