题目描述

给出 $n$ 个正整数 $x_{1\dots n}$，可以进行不超过 $m$ 次操作，每次操作选择一个非零的 $x_i$，并将它减一。

最终要求存在某个 $k$ 满足 $x_k=0$，并且 $z=\max\limits_{1\leq i<n}\{|x_i-x_{i+1}|\}$ 最小。

输出最小的 $z$ 和此时最小的 $k$。

输入格式

第一行两个正整数 $n,m$。
第二行 $n$ 个正整数 $x_{1\dots n}$。

输出格式

输出一行两个整数 $k$ 和 $z$。
数据保证方案一定存在。

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

1 2

样例解释

将 $x$ 序列变为 $\rm 0, 2, 4, 5, 5, 5, 5, 5, 6, 6, 7, 8, 9, 7, 5, 5$。
此时 $k=1$，$z=2$，共操作了 $8+5+2=15$ 次。

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$1\leq m\leq 10^{18}$，$1\leq x_i\leq 10^9$。