佬姜大厦
题号:NC219227
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

每天,佬姜都要前往佬姜大厦的顶层工作。作为佬姜家族企业的继承者,佬姜每天的工作内容就是前往佬姜大厦的顶层参与家族会议,做决策,闲暇时间就在顶层的办公室AK比赛。

佬姜大厦有  层,非常高!并且由于佬姜的直升机正在进行升级改造,佬姜只能乘坐电梯前往大厦的顶层。坐电梯就意味着不得不与其他佬姜大厦的员工一起挤电梯。挤电梯又热又闷,而且电梯时常要在中间的楼层停下,极其耽误时间。

为了节省时间,处于一楼的佬姜走进电梯,以佬姜家族企业继承者的身份命令电梯里的位员工:

1、      在抵达顶层前,电梯至多只能停次;

2、      不允许新的乘客进入电梯;

3、      员工不允许在顶层离开电梯。

可是,这个员工想要前往的楼层并不相同,只停次怎么够!于是,众员工共同商讨,决定让电梯在个选定的楼层停留。每个员工可以在这个选定的停留楼层中离开电梯,然后如果需要的话,走楼梯前往他想去的楼层。员工也可以选择在层直接离开电梯,走楼梯前往他想去的楼层。

公平起见,大家希望选出个电梯停靠的楼层,使需要走楼梯层数最多的人需要走楼梯的层数最小。你将来肯定是要为佬姜打工的,所以你现在算一下需要走楼梯层数最多的人需要走楼梯的层数最小是多少也是未雨绸缪。

输入描述:

第一行输入三个整数,分别表示佬姜大厦有层,一层的电梯里此时有位员工,佬姜允许电梯最多停次。

第二行包括个整数,表示第位员工想要前往第a_i层。

输出描述:

输出仅包括一个数字,表示需要走楼梯层数最多的人需要走楼梯的层数最小是多少。

示例1

输入

复制
12 5 3
2 3 5 7 11

输出

复制
1

说明

让电梯在4层、7层和11层停靠。
这样,第一位员工从1层出发,须走楼梯1层;
第二位员工从4层出发,须走楼梯1层;
第三位员工从4层出发,须走楼梯1层;
第四位员工从7层出发,不需要走楼梯;
第五位员工从11层出发,不需要走楼梯。
须走楼梯层数最多的人须走1层。该电梯停靠方案是一种最优方案。