CF1835B.Lottery

$n$ people indexed with integers from $1$ to $n$ came to take part in a lottery. Each received a ticket with an integer from $0$ to $m$.

In a lottery, one integer called target is drawn uniformly from $0$ to $m$. $k$ tickets (or less, if there are not enough participants) with the closest numbers to the target are declared the winners. In case of a draw, a ticket belonging to the person with a smaller index is declared a winner.

Bytek decided to take part in the lottery. He knows the values on the tickets of all previous participants. He can pick whatever value he wants on his ticket, but unfortunately, as he is the last one to receive it, he is indexed with an integer $n + 1$.

Bytek wants to win the lottery. Thus, he wants to know what he should pick to maximize the chance of winning. He wants to know the smallest integer in case there are many such integers. Your task is to find it and calculate his chance of winning.

有 $n$ 个人参加一场抽奖活动，他们的编号为 $1$ 到 $n$。每人获得一张票，票上写有一个从 $0$ 到 $m$ 的整数。

在抽奖中，一个称为“目标值”（target）的整数会从 $0$ 到 $m$ 中均匀随机抽取。与目标值最接近的 $k$ 张票（若参与者不足 $k$ 人，则取全部）被宣布为中奖票。若出现距离相等的平局情况，则编号更小的人所持的票获胜。

Bytek 决定参加这场抽奖。他已知此前所有 $n$ 位参与者所持票上的数值。他可以自由选择自己票上的整数，但不幸的是，由于他是最后一位领票者，他的编号为 $n + 1$。

Bytek 希望赢得抽奖，因此他希望选择一个能最大化其中奖概率的整数。若存在多个这样的整数，则应选择其中最小的整数。你的任务是找出该整数，并计算 Bytek 此时的中奖概率。

In the first line of the input, there are the integers $n$, $m$, and $k$ ($1 \leq n \leq 10^6$, $0 \leq m \leq 10^{18}$, $1 \leq k \leq 10^6$).

In the following line, there are $n$ integers separated by a single space, denoting the numbers on tickets received by people participating in a lottery. These numbers are integers in the range from $0$ to $m$.

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n \leq 10^6$，$0 \leq m \leq 10^{18}$，$1 \leq k \leq 10^6$）。

接下来的一行包含 $n$ 个用单个空格分隔的整数，表示参与抽奖活动的人所获得的彩票上的数字。这些数字均为介于 $0$ 到 $m$（含）之间的整数。

You should output two integers separated by a single space on the standard output. The first should be equal to the number of target values (from $0$ to $m$), upon drawing which Baytek wins, given that he chooses his ticket optimally. The second should be equal to the integer Bytek should pick to maximize his chance of winning the lottery.

你应在标准输出中输出两个由单个空格分隔的整数。第一个整数应等于目标值（从 $0$ 到 $m$）的个数，使得当抽到这些目标值时，Baytek 在最优选择彩票的前提下获胜；第二个整数应等于 Bytek 为最大化其中奖概率所应选取的整数。

In the first example, Bytek wins for $4$ target values (namely $0, 1, 2, 3$) if he chooses integer $2$, which is the lowest optimal value. If he chooses $3$, he also wins in four cases, but it is not the lowest value.

在第一个例子中，如果 Bytek 选择整数 $2$（即最低的最优值），则他在 $4$ 个目标值（即 $0, 1, 2, 3$）的情况下获胜。如果他选择 $3$，同样能在四种情况下获胜，但它并非最低的值。