4069. 又是决斗

【题目描述】

今天是小 Q 的生日，他得到了 $n$ 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”，其中，第 $i$ 张卡代表一只攻击力为 $r_i$，防御力也为 $r_i$ 的怪兽。

一场游戏分为若干回合。每回合，小 Q 会选择某只怪兽 $i$ 以及另一只怪兽 $j(i \neq j)$，并让怪兽 $i$ 向怪兽 $j$ 发起攻击。此时，若怪兽 $i$ 的攻击力小于等于怪兽 $j$ 的防御力，则无事发生；否则，怪兽 $j$ 的防御被打破，怪兽 $j$ 退出游戏不再参与到剩下的游戏。怪兽 $i$也因为元气大伤不能继续参加游戏。 一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽都不能发起过攻击时，游戏结束。

小 Q 希望决定一组攻击顺序，使得在游戏结束时，未退出游戏的怪兽数量尽可能少。

【输入格式】

输入的第一行包含一个正整数 $n$，表示卡牌的个数。

输入的第二行包含 $n$ 个正整数，其中第 $i$ 个正整数表示第 $i$ 个怪兽的攻击力及防御力 $r_i$。

【输出格式】

输出一行包含一个整数表示游戏结束时未退出游戏的怪兽数量的最小值。

【样例1输入】

5
1 2 3 1 2

【样例1输出】

1

【样例1说明】

其中一种最优方案为：第一回合让第 $2$ 只怪兽向第 $1$ 只怪兽发起攻击，第二回合让第 $5$ 只怪兽向第 $4$ 只怪兽发起攻击，此时只剩下一只怪兽，无法发起攻击，游戏结束。可以证明没有更优的攻击顺序。

【样例2输入】

10
136 136 136 2417 136 136 2417 136 136 136

【样例2输出】

6

【大样例】

大样例

【数据规模与约定】

对于20%测试数据，保证：$1 \leq n \leq 10^2$，$1 \leq r_i \leq 10^5$。

对于所有测试数据，保证：$1 \leq n \leq 7×10^6$，$1 \leq r_i \leq 10^9$。