Lottery
Contest: Codeforces Round 880 (Div. 1)
Difficulty rating: 2500
Tags: binary search, brute force, greedy, math, two pointers

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
3 6 2
1 4 5

Example output:
4 2

Example input:
7 7 1
2 4 7 3 0 1 6

Example output:
1 5

Editorial:
Let's assume that Bytek has selected a certain position $$$c$$$. Let the closest occupied position to the left be $$$d$$$, and the closest occupied position to the right be $$$e$$$. Let's denote the position of the $$$k$$$-th person to the left as $$$a$$$ and the $$$k$$$-th person to the right as $$$b$$$ (on the picture $$$k=3$$$).
Note that for Bytek to win, the target position should be closer to him than $$$a$$$ and closer to him than $$$b$$$. So his winning range is in the interval $$$(\frac{a+c}{2}, \frac{b+c}{2})$$$. It will either have a length of $$$\lfloor \frac{b-a}{2}-1 \rfloor$$$ or $$$\lfloor \frac{b-a}{2}-2 \rfloor$$$, which depends only on whether he chooses an even or odd position relative to the people on positions $$$a$$$ and $$$b$$$.
So the solution to the task was to consider each pair of people standing next to each other and see what happens if Bytek stands between them. To do this, we find the person $$$k$$$ positions to the left and $$$k$$$ positions to the right for Bytek and then check what the result will be if Bytek stands on the leftmost position inside this interval and what if Bytek stands on the second position from the left inside this interval. The other positions in this interval would give Bytek the same results but wouldn't be the leftmost.
In addition, we should look at what would happen if Bytek stood in a position where someone is already standing (this may help if there is not enough space between consecutive people). There are also two more edge cases – from the left and the right. One of these cases is to look at what would happen if Bytek stands one or two positions in front of the $$$k$$$-th person from the left. This position would give Bytek the biggest winning range containing $$$0$$$. The other case is analogous from the right.
The final complexity is $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(n \log n)$$$ based on implementation.