题目内容

园丁阿明有一排共 $n$ 朵花，从左到右编号为 $1$ 到 $n$。第 $i$ 朵花的初始高度为 $h_i$ 厘米。

每天他可以挑选一朵花，给它浇水，使其高度增加 $1$ 厘米。他最多可以进行 $k$ 次浇水操作，且可以对同一朵花多次浇水。

阿明希望经过若干次操作后，使相邻花朵高度之差的绝对值的最大值尽可能小。换句话说，令最终高度序列为 $h'_1, h'_2, \dots, h'_n$，目标是最小化 $\max_{1 \le i < n} |h'_i - h'_{i+1}|$。请你计算这个最小值是多少。

数据范围：花朵数量 $n$ 满足 $2 \le n \le 10^5$，操作次数 $k$ 满足 $0 \le k \le 10^9$，初始高度 $h_i$ 满足 $1 \le h_i \le 10^9$。测试数据组数 $T$ 不超过 $100$。

输入描述