分数: 700 点
问题陈述
N 为即将举行的比赛提出问题。问题 i 的初始整数分数为 A_i 点。
M 评委们即将投票选出他们喜欢的问题。每位评委都会准确选择 V 问题,独立于其他法官, 并将每个选定问题的分数增加 1.
毕竟 M 评委投票,问题按照分数不升序排列,排名第一的 将选择 P 问题作为问题集。 分数相同的题目可以任意排序,这个顺序由主审决定。
给定的问题有多少 N 有机会被选为问题集吗?
约束
- 2 \le N \le 10^5
- 1 \le M \le 10^9
- 1 \le V \le N - 1
- 1 \le P \le N - 1
- 0 \le A_i \le 10^9
输入
输入由标准输入按以下格式给出:
N M V P A_1 A_2 ... A_N
输出
打印有机会被选择作为问题集的问题数。
示例输入 1
6 1 2 2 2 1 1 3 0 2
示例输出 1
5
如果唯一的法官投票给问题 2 和 5,分数将为 2 2 1 3 1 2。 问题集将包含问题 4 和问题之一 1, 2,或 6.
如果唯一的法官投票给问题 3 和 4,分数将为 2 1 2 4 0 2。 问题集将包含问题 4 和问题之一 1, 3,或 6.
因此,问题 1, 2, 3, 4,和 6 有机会被选为问题集。反之则没有办法解决问题 5 待选择。
示例输入 2
6 1 5 2 2 1 1 3 0 2
示例输出 2
3
只有问题 1, 4,和 6 有机会被选中。
示例输入 3
10 4 8 5 7 2 3 6 1 6 5 4 6 5
示例输出 3
8