CF1835B Lottery

有 $n$ 个人，编号为 $1$ 到 $n$，来参加抽奖。每个人都收到了一张写有 $0$ 到 $m$ 之间整数的票。 在抽奖中，将从 $0$ 到 $m$ 之间均匀随机抽取一个整数作为目标数。与目标数最接近的 $k$ 张票（如果参与者不足 $k$ 人，则全部参与者）获胜。如果有多人距离目标数相同，则编号较小的人获胜。 Bytek 决定参加抽奖。他知道所有前面参与者票上的数字。他可以选择自己票上的任意数字，但由于他是最后一个拿到票的人，他的编号为 $n+1$。 Bytek 想要赢得抽奖。因此，他想知道应该选择哪个数字，才能最大化自己获胜的概率。如果有多个这样的数字，他想知道最小的那个。你的任务是找出这个数字，并计算他获胜的目标数的数量。

输入的第一行包含整数 $n$、$m$ 和 $k$（$1 \leq n \leq 10^6$，$0 \leq m \leq 10^{18}$，$1 \leq k \leq 10^6$）。 接下来一行有 $n$ 个用空格分隔的整数，表示每个参与者票上的数字，这些数字在 $0$ 到 $m$ 之间。

你需要输出两个用空格分隔的整数。第一个是 Bytek 在最优选择下能获胜的目标数（即从 $0$ 到 $m$ 中，抽到这些目标数时 Bytek 获胜），第二个是他应选择的最小整数。

在第一个样例中，如果 Bytek 选择数字 $2$，那么当目标数为 $0, 1, 2, 3$ 时他会获胜，共有 $4$ 种情况，这是最优且最小的选择。如果他选择 $3$，同样可以获胜 $4$ 次，但不是最小的选择。 由 ChatGPT 4.1 翻译