우물 파기

바이테아사르는 바이토시아 사막을 가로지르는 마른 강을 따라 여행을 떠났습니다. 그런데 강물이 완전히 말라버렸고, 바이테아사르는 마실 물마저 다 떨어졌습니다. 이제 유일한 희망은 말라붙은 강바닥에 우물을 충분히 깊게 파서 지하수에 도달하는 것입니다.

상황이 위급하다는 것을 깨달은 바이테아사르는 삽질을 시작하기 전에 계획을 신중히 세우기로 합니다. 가장 큰 위험은 지하수에 닿기도 전에 체력이 바닥나는 것이고, 그렇게 되면 살아남기 어렵습니다. 그는 지하수까지의 깊이를 알아냈고, 체력이 다하기 전까지 삽을 몇 번이나 휘두를 수 있는지도 알고 있습니다. 또 다른 걱정거리는 산사태이므로, 파낸 구덩이의 경사를 최대한 완만하게 유지하고 싶어 합니다. 그는 위성 전화로 강바닥의 지형도를 보내며, 어디를 파야 할지 조언을 구하고 있습니다.

첫째 줄에 두 양의 정수 $n$과 $m$이 공백 하나로 구분되어 주어집니다 ($1 \le n \le 1\,000\,000$, $1 \le m \le 10^{18}$).

둘째 줄에 $n$개의 양의 정수 $x_1, x_2, \dots, x_n$이 공백으로 구분되어 주어집니다 ($1 \le x_i \le 10^9$).

바이테아사르는 삽을 $m$번 휘두를 수 있는 체력을 가지고 있습니다. 수열 $x_1, x_2, \dots, x_n$은 강바닥의 지형을 나타내며, 강바닥을 따라 1미터 간격으로 놓인 각 지점에서 지하수면 위에 쌓인 모래층의 깊이입니다. 삽을 한 번 휘두를 때마다 임의의 $x_i$ 하나를 $1$만큼 줄일 수 있습니다. 어떤 $x_k$가 $0$이 되면, 그 지점에서 지하수에 도달한 것입니다.

바이테아사르는 또한 모래 언덕의 경사를 나타내는 다음 값 $z$를 최소로 만들고 싶어 합니다.

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

여기서 $x_i$는 삽질을 모두 끝낸 뒤의 최종 깊이를 뜻합니다. 팔 수 있는 지점은 $1, 2, \dots, n$뿐이며, 그 밖의 장소는 모래가 아니라 바위입니다. 바이테아사르에게는 적어도 한 지점에서 지하수에 도달할 만큼의 체력이 있다고 가정해도 좋습니다.

최소 경사 $z$를 달성하면서 우물을 팔 수 있는 지점 $k$가 여러 개일 수 있습니다. 그중 가장 작은(가장 왼쪽) 지점을 답합니다.

표준 출력에 두 정수를 공백 하나로 구분하여 출력하세요. 첫째는 최소 경사 $z$를 유지하면서 지하수에 도달할 수 있는 가장 작은 지점 번호 $k$(1부터 시작), 둘째는 그때의 최소 경사 값 $z$입니다.

위 그림에서 바이테아사르가 할 수 있는 가장 좋은 굴착 모양이 회색으로 표시되어 있습니다.