[Poi2012]Well

时间限制:40s      空间限制:64MB

题目描述

 给出n个正整数X1,X2,...Xn,可以进行不超过m次操作,每次操作选择一个非零的Xi,并将它减一。

最终要求存在某个k满足Xk=0,并且z=max{|Xi - Xi+1|}最小。
输出最小的z和此时最小的k。



输入格式

 

第一行两个正整数n, m (1<=n<=1,000,000, 1<=m<=10^18)。第二行n个正整数X1,X2,...Xn (Xi<=10^9)。



输出格式

 

输出k和z。数据保证方案一定存在。



样例输入

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


样例输出

1 2


提示

 将X序列变为

0 2 4 5 5 5 5 5 6 6 7 8 9 7 5 5
此时k=1,z=2,共操作了8+5+2=15次。


题目来源

鸣谢 oimaster