問題文
Snuke 和 Sumeke 决定使用编号卡和硬币玩以下游戏。
首先,Snuke
一张写有 T 的卡片,并且 K 硬币,Sumeke先生给了一张卡片。
我有 N 。
这个游戏是
分为 N 轮,Sumeke每轮执行一次以下步骤。
- Sumeke先生选择了一张他尚未向Snuke展示的牌并向他展示。这张卡上写的号码 A 。 上线
- Snuke 持有的卡片上写的号码 B 那么,Snuke-kun是Sumeke-san的。|A-B| 受到伤害。
- 当 Snuke 有金币时,给 Sumeke 一枚金币。 A 卡 要么用它交换一张 B 卡,要么不给金币什么也不做。
所以,Snuke君发现了Sumeke-san的策略,而Sumeke-san并不关心Snuke-kun的行动。 i 写入的值 我确信他会打出 A_i 牌。
求 Snuke 在每轮中受到的最小可能最大伤害。
然而,每回合结束后,Sumeke 都会恢复 Snuke 的伤害。
入力
输入将以以下格式从标准输入提供。
N T K A_1 A_2 ... A_N
- 第一行是轮数。 N(1≦N≦100,000)您拥有的第一张卡片上写的号码 T(1≦T≦10^{9}), 硬币数量 K(1≦K≦N) 。 来自行
- 下一行是 给定N 数字,i Sumeke 作为整数 i(1≦i≦N) 第一次玩时写在卡上的号码 A_{i}(1≦A_{i}≦10^{9}) 。 来自行
配点
这个问题有部分要点。作为附加约束, 如果您在满足 N=K 的情况下解决了此问题,您将获得20分。
出力
在一行中,打印 Snuke 在每一轮中受到的最小可能最大伤害。 在末尾插入换行符。入力例1
5 1 1 1 2 3 4 5
出力例1
2
入力例2
8 9 3 11 4 5 14 19 19 8 10
出力例2
6