Digging a Well

Byteasar has set off on a journey along the Dry River, which crosses the Byteotian Desert. Unfortunately the Dry River has completely dried out, and Byteasar has run out of water. His only hope is to dig a well deep enough in the dried river bed to reach the groundwater.

Realising how grave his situation is, Byteasar decides to plan everything carefully before he starts digging. The greatest danger is that he drains his strength before reaching the water level, in which case he is unlikely to survive. He has determined the depth of the water level, and he knows how many shovel swings he can make before losing his strength. His other worry is a possible landslide, so he wants the slope of his excavation to be as gentle as possible. He sends you a topographic map of the river bed over a satellite phone and asks for your advice on where to dig.

The first line of standard input contains two positive integers $n$ and $m$, separated by a single space ($1 \le n \le 1\,000\,000$, $1 \le m \le 10^{18}$).

The second line contains $n$ positive integers $x_1, x_2, \dots, x_n$, separated by single spaces ($1 \le x_i \le 10^9$).

Byteasar has enough strength to make $m$ swings of the shovel. The numbers $x_1, x_2, \dots, x_n$ describe the topography of the river bed: they give the depth of the sand layer above the groundwater level at successive spots spaced one meter apart. A single swing of the shovel lets Byteasar decrease any one $x_i$ by $1$. If some $x_k$ drops to $0$, he has dug down to the water at that spot.

Byteasar also wants to minimise the value $z$, which measures the steepness of the sand profile:

$z = \max_{1 \le i \le n-1} |x_i - x_{i+1}|$

Here the $x_i$ denote the final depths after all digging is done. Only the spots $1, 2, \dots, n$ can be dug; everywhere else there is rock rather than sand. You may assume that Byteasar has enough strength to reach the water at one of the spots.

There may be several spots $k$ at which Byteasar can dig while achieving the minimum slope $z$. Report the smallest (leftmost) such spot.

Print two integers separated by a single space: the smallest spot number $k$ (1-based) at which he can reach the water while attaining the minimum slope $z$, and that minimum slope value $z$.

In the figure above, the best excavation Byteasar can make is marked in grey.