题目描述

一群小学生在玩一个名为“谁是大赢家”的游戏。该游戏按如下规则进行： 共 n 个人参与该游戏，每个人一开始会得到 n 颗石头。接着，从第一个人开始，轮流进 行操作。针对第 i 个人，其操作流程如下：

（1）挑选 k=min(x-1,a[i])个不同的人，其中 x 为此时现存人数

（2）被挑中的 k 个人每个人给第 i 个人 1 颗石子

（3）如果某个人手中不再有石子给别人，则其被淘汰出局

大家都不希望自己出局，并且希望有尽可能多的人出局，游戏无限的进行下去，问最终 游戏中最少还有几个人没有出局。

输入格式

第一行输入一个数字 n， 代表游戏的总人数。接下来输入 n 个数字，分别代表 ai

输出格式

输出一行一个整数表示游戏最终最少剩几个人。

2
1 2

2

</p>

提示

【样例 1 说明】

两个人只能互相拿对方的 1 颗石子，游戏永远进行下去。

【数据范围】

对于 20% 的数据，满足 n≤ 2；

对于 40% 的数据，满足 n ≤ 3；

对于 100% 的数据，满足 1 ≤ n ≤ 10⁵, 1 ≤ a[i]≤ 10⁹。

来源

2023年六年级集训队选拔测