Byteasar 踏上了沿着干涸的河流穿越 Byteotian 沙漠的旅程。不幸的是，这条河已经干涸，Byteasar 的水也喝光了。他唯一的希望是在干涸的河床上挖一口足够深的井。

意识到情况的严重性，Byteasar 决定在开始挖掘之前仔细规划一切。危险在于他可能会在到达水位之前耗尽体力——在这种情况下，他很难存活。他已经确定了水位深度，也知道自己在体力耗尽前能挖多少次。他唯一担心的是可能发生的滑坡，这可能会将他活埋。他通过卫星电话向你发送了一份河床的地形图。当然，他请求你帮助他确定应该在哪里挖掘，以便在耗尽体力之前到达水位，同时尽可能保持挖掘坡度平缓。他正在等待你的建议！

输入格式

第一行包含两个正整数 $n$ 和 $m$ ($1 \le n \le 1,000,000$, $1 \le m \le 10^{18}$)，中间用一个空格隔开。第二行包含 $n$ 个正整数 $x_1, x_2, \ldots, x_n$ ($1 \le x_i \le 10^9$)，同样用空格隔开。

Byteasar 有足够的体力进行 $m$ 次铲土。数字 $x_1, x_2, \ldots, x_n$ 描述了干涸河床的地形。它们代表了沿河床每隔一米处沙层距离地下水位的深度。每铲一次土，Byteasar 可以将任意一个 $x_i$ 的值减 1。如果其中某个数字（例如 $x_k$）降为 0，则意味着 Byteasar 已经挖到了水。但 Byteasar 还有一个次要目标。他希望最小化以下代表沙丘坡度的数字 $z$：

$$z = \max_{i=1,2,\ldots,n-1} \left| x_i - x_{i+1} \right| $$

如果存在多个正确的 $k$ 值（代表 Byteasar 挖掘并到达水位的地点），你的程序可以任意选择其中一个。地点 $1, 2, \ldots, n$ 是唯一适合挖掘的地方——其他地方是岩石而非沙子。你可以假设 Byteasar 有足够的体力在其中一个地点挖到水。

在至少占 $35\%$ 分值的测试点中，满足 $n \le 10,000$。

输出格式

你的程序应向标准输出打印两个整数，中间用一个空格隔开：Byteasar 应该挖掘的地点 $k$，以及数字 $z$ 的最小值。

样例

样例输入 1

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

样例输出 1

1 2

在上图中，Byteasar 能做出的最佳挖掘方案用灰色标出。