小 Z 的传球游戏
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
校运动会开始了,小 Z 作为学校篮球队教练,准备在运动会前训练他的校队队员。
现在有 共 名队员排成一条直线,第 个人在 位置(可以想象成一个数轴上有 个点,每个点的位置为 ),其中每个人都在不同的位置上。
现在,小 Z 准备让这些队员进行传球训练,初始时,这些队员手上没有球,他会把球传给若干个队员,然后这些队员会把球传给离他们最近的人。
- 具体来讲,编号为 的队员在接到球的时候,会把球传给离他最近的队员,如果有多个队员离他的距离相同且最近,那么他就会传给 最小(最左边)的队员。
- 注意: 号队员接到球的时候,无论是来自小 Z 的还是其他队员的,他都一定要把球再传出去。
为了保证训练效果,每个队员都必须要拿到球至少一次,请你帮助小 Z 确定最少需要准备几个球才能达到这个效果。换句话说,小 Z 在最开始的时候最少需要给几个队员准备球。
输入格式
第一行输入一个正整数 表示队员数量。
第二行输入 个正整数, 表示这 个队员的初始位置。
输出格式
输出一个正整数 表示小 Z 在最开始最少需要给几个队员球,才可以使得每个队员至少接到一次球。
输入输出样例
5
7 1 3 11 4
2
提示
【样例解释】
小 Z 在最开始会给 号以及 号球,也就是 的人会拿到球。
- 的人会把他的球传给 的人,然后这个球会在 的人和 的人之间来回传递。
- 的人会把他的球传给 的人,然后球会被传给 的人,然后这个球又会在位于 的人和位于 的人之间来回传递。
- 保证了所有人都接到球至少一次,并且通过枚举可以证明,这是初始球数最少的方案。
【数据范围】
,且保证每个 互不相同。