题目描述

Byteasar has set off on a journey along the Dry River, which crosses the Byteotian Desert.

Unfortunately, the Dry River has dried out, and Byteasar has run out of water.

His only hope is to dig a deep enough well in the dried river bed.

Realising the graveness of his situation, Byteasar decides to plan everything carefully before he actually starts digging.

The danger is that he drains his strength before he reaches the water level - in such case he is unlikely to survive.

He managed to determine the depth of the water level. He also knows how much he can dig before losing strength.

His only worry is a possible landslide, which might bury him alive.

He sends you (via a satellite telephone) a topographic map of the river bed.

And, of course, he asks you to help him determine where he should dig so that he reaches water before draining his strength while keeping the slope of his excavation as gentle as possible.

He is waiting for your advice!

输入格式

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

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

Byteasar has enough energy to perform $m$ swings of the shovel.

The numbers $x_1,x_2,\cdots,x_n$ describe the topography of the Dry River's bed.

They represent the depth of the sand layer above the ground water level in successive one meter spaced spots along the river bed.

With a single swing of the shovel Byteasar can extract an amount of the sand that decreases any of the numbers $x_i$ by 1.If any of these numbers, say $x_k$, drops to 0, this means that Byteasar has dug down to the water. But Byteasar has a secondary goal as well. He wants the following number $z$, characterising the slope of the sand hill, minimised:

$z=max_{i=1,2,\cdots,n-1}|x_i-x_{i+1}|$ If there are multiple correct values of the number $k$,representing the spot where Byteasar is to dig down to reach the water, your program can pick one arbitrarily. The spots $1,2,\cdots,n$ are the only ones suitable for digging - elsewhere there is rock rather than sand. You may assume that Byteasar has enough energy to reach water at one of the spots.

输出格式

Your program should print two integers to the standard output, separated by a single space:

the spot $k$, where Byteasar should dig for water, and the minimum value of the number $z$.

题目大意

给定一个非负整数序列 $A$，每次操作可以选择一个数然后减掉 $1$，要求进行不超过 $m$ 次操作使得存在一个 $A_k=0$ 且 $\max(|x_i-x_{i-1}|)$ 最小，输出使其最小的 $k$ 与这个最小值。

16 15
8 7 6 5 5 5 5 5 6 6 7 8 9 7 5 5

1 2