310448: CF1835B. Lottery

B. Lotterytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

$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.

Input

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$.

Output

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.

ExamplesInput

3 6 2
1 4 5

Output

4 2

Input

7 7 1
2 4 7 3 0 1 6

Output

1 5

Note

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.

题目大意：
这是一道关于彩票的题目。有n个人参与彩票，每个人获得一张0到m之间的整数票。彩票的中奖号码（target）从0到m中均匀抽取。最接近中奖号码的k张票（如果参与者不足k人，则取实际人数）的持有者被宣布为中奖者。如果有并列，则索引号较小的人获胜。Bytek是最后一个参与者，他的索引号是n+1。Bytek想知道他应该选择什么号码才能最大化他获胜的机会，同时他想知道如果有多个这样的数字，应该选择最小的那一个。任务是找出这个数字并计算他获胜的概率。

输入输出数据格式：
输入：
- 第一行包含三个整数n、m和k（1≤n≤10^6，0≤m≤10^18，1≤k≤10^6）。
- 下一行包含n个由单个空格分隔的整数，表示参与彩票的人收到的票上的数字。这些数字是0到m之间的整数。

输出：
- 在标准输出上输出两个由单个空格分隔的整数。第一个数应该是Bytek选择最佳号码时，他获胜的目标值（从0到m）的数量。第二个数应该是Bytek为了最大化获胜机会应该选择的整数。

示例：
输入：
3 6 2
1 4 5
输出：
4 2

输入：
7 7 1
2 4 7 3 0 1 6
输出：
1 5

注意：
在第一个示例中，如果Bytek选择整数2，他将在4个目标值（即0、1、2、3）的情况下获胜，这是最佳选择中的最低值。如果他选择3，他也会在4个情况下获胜，但这不是最低值。题目大意： 这是一道关于彩票的题目。有n个人参与彩票，每个人获得一张0到m之间的整数票。彩票的中奖号码（target）从0到m中均匀抽取。最接近中奖号码的k张票（如果参与者不足k人，则取实际人数）的持有者被宣布为中奖者。如果有并列，则索引号较小的人获胜。Bytek是最后一个参与者，他的索引号是n+1。Bytek想知道他应该选择什么号码才能最大化他获胜的机会，同时他想知道如果有多个这样的数字，应该选择最小的那一个。任务是找出这个数字并计算他获胜的概率。 输入输出数据格式： 输入： - 第一行包含三个整数n、m和k（1≤n≤10^6，0≤m≤10^18，1≤k≤10^6）。 - 下一行包含n个由单个空格分隔的整数，表示参与彩票的人收到的票上的数字。这些数字是0到m之间的整数。 输出： - 在标准输出上输出两个由单个空格分隔的整数。第一个数应该是Bytek选择最佳号码时，他获胜的目标值（从0到m）的数量。第二个数应该是Bytek为了最大化获胜机会应该选择的整数。 示例： 输入： 3 6 2 1 4 5 输出： 4 2 输入： 7 7 1 2 4 7 3 0 1 6 输出： 1 5 注意： 在第一个示例中，如果Bytek选择整数2，他将在4个目标值（即0、1、2、3）的情况下获胜，这是最佳选择中的最低值。如果他选择3，他也会在4个情况下获胜，但这不是最低值。