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

# [CSP-S 2024] 决斗rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
## 题目描述rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
今天是小 Q 的生日，他得到了 $n$ 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”，其中，第 $i$ 张卡代表一只攻击力为 $r_i$，防御力也为 $r_i$ 的怪兽。rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一场游戏分为若干回合。每回合，小 Q 会选择某只怪兽 $i$ 以及**另一只**怪兽 $j(i \neq j)$，并让怪兽 $i$ 向怪兽 $j$ 发起攻击。此时，若怪兽 $i$ 的攻击力小于等于怪兽 $j$ 的防御力，则无事发生；否则，怪兽 $j$ 的防御被打破，怪兽 $j$ 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中**至多**只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时，游戏结束。rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
小 Q 希望决定一组攻击顺序，使得在游戏结束时，未退出游戏的怪兽数量尽可能少。rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
## 输入格式rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入的第一行包含一个正整数 $n$，表示卡牌的个数。rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入的第二行包含 $n$ 个正整数，其中第 $i$ 个正整数表示第 $i$ 个怪兽的攻击力及防御力 $r_i$。rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
## 输出格式rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出一行包含一个整数表示游戏结束时未退出游戏的怪兽数量的最小值。rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
## 样例 #1rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
### 样例输入 #1rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
```rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 2 3 1 2rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
```rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
### 样例输出 #1rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
```rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
```rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
## 样例 #2rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
### 样例输入 #2rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
```rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
10rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
136 136 136 2417 136 136 2417 136 136 136rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
```rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
### 样例输出 #2rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
```rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
8rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
```rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
## 提示rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
**【样例 1 解释】**rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
其中一种最优方案为：第一回合让第 $2$ 只怪兽向第 $1$ 只怪兽发起攻击，第二回合让第 $5$ 只怪兽向第 $4$ 只怪兽发起攻击，第三回合让第 $3$ 只怪兽向第 $5$ 只怪兽发起攻击。此时没有退出游戏的怪兽都进行过攻击，游戏结束。可以证明没有更优的攻击顺序。rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
**【样例 3】**rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
见选手目录下的 duel/duel3.in 与 duel/duel3.ans。rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
该样例满足 $\forall 1 \leq i \leq n, r_i \leq 2$。rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
**【样例 4】**rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
见选手目录下的 duel/duel4.in 与 duel/duel4.ans。rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
**【数据范围】**rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于所有测试数据，保证：$1 \leq n \leq 10^5$，$1 \leq r_i \leq 10^5$。rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
| 测试点 | $n$ | $r_i$ | 特殊性质 |rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
| :----------: | :----------: | :----------: | :----------: |rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
| $1\sim 4$ | $\leq 10$ | $\leq 10^5$ | 无特殊性质 |rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
| $5\sim 10$ | $\leq 10^5$ | $\leq 2$ | 无特殊性质 |rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
| $11\sim 15$ | $\leq 30$ | $\leq 10^5$ | 特殊性质 A |rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
| $16\sim 20$ | $\leq 10^5$ | $\leq 10^5$ | 无特殊性质 |rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
rUt100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
特殊性质 A：保证每个 $r_i$ 在可能的值域中独立均匀随机生成。