背景

CSP-S 2024 T1

题目描述

今天是小 Q 的生日，他得到了 n 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”，其中，第i 张卡代表一只攻击力为 ri ，防御力也为ri​的怪兽。一场游戏分为若干回合。每回合，小 Q 会选择某只怪兽 i 以及另一只怪兽 j(i≠j)，并让怪兽 i 向怪兽 j 发起攻击。此时，若怪兽 i 的攻击力小于等于怪兽 j 的防御力，则无事发生；否则，怪兽 j 的防御被打破，怪兽 j 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时，游戏结束。

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

格式

输入格式

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

输出格式

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

Samples

5
1 2 3 1 2

2

10
136 136 136 2417 136 136 2417 136 136 136

8

说明