比赛结束后,詹感到很累,他把比赛中唯一没有解决的任务交给了他的朋友 Sungat。但是,他也无法解决,所以我们请您尝试解决这个问题。
给定一个数组 $$$a_1, a_2, \ldots, a_n$$$,长度为 $$$n$$$。我们可以对数组执行任意数量(可能为零)的操作。
在一次操作中,我们选择一个位置 $$$i$$$ ($$$1 \leq i \leq n - 1$$$) 并执行以下操作:
- $$$a_i := a_i - 1$$$ 和 $$$a_{i+1} := a_{i+1} + 1$$$。
求 $$$\max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)$$$ 的最小可能值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{12}$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数:$$$\max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)$$$ 的最小可能值。
示例
输入 #1
5 1 1 3 1 2 3 4 4 1 2 3 4 4 2 3 1 5 5 14 4 10 2
输出 #1
0 2 1 1 3
注意
在第三个测试用例中,您可以使用 $$$i = 1$$$ 执行该操作两次。
之后,数组为 $$$a = [2, 3, 2, 3]$$$ 和 $$$\max(2, 3, 2, 3) - \min(2, 3, 2, 3) = 3 - 2 = 1$$$。