题目描述

译自 POI 2012 Stage 1. 「Well」

给定 $n$ 个正整数 $x_1, x_2, \ldots, x_n$，可以进行不超过 $m$ 次操作，每次操作时选择一个正整数 $x_i$ 并将其减一。

在存在 $k$ 使得 $xk=0$ 的情况下，最小化 $$ z = \max{i=1,2,\ldots,n-1}{\lvert xi - x{i+1} \rvert} $$

求最小的 $z$ 和对应的 $k$。如果有多组解，可以输出任意一组。

输入格式

第一行两个正整数 $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)$。

输出格式

输出两个正整数，分别表示 $k$ 和 $z$。

样例

input

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

output

1 2

数据范围与提示

对于 $35\%$ 的数据，$n \le 10\ 000$；

对于所有数据，$1 \le n \le 1\ 000\ 000, 1 \le m \le 10^{18},1 \le x_i \le 10^9$。