D. Minimize the Difference
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Zhan, tired after the contest, gave the only task that he did not solve during the contest to his friend, Sungat. However, he could not solve it either, so we ask you to try to solve this problem.

You are given an array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$. We can perform any number (possibly, zero) of operations on the array.

In one operation, we choose a position $$$i$$$ ($$$1 \leq i \leq n - 1$$$) and perform the following action:

  • $$$a_i := a_i - 1$$$, and $$$a_{i+1} := a_{i+1} + 1$$$.

Find the minimum possible value of $$$\max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{12}$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer: the minimum possible value of $$$\max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)$$$.

Example
Input
5
1
1
3
1 2 3
4
4 1 2 3
4
4 2 3 1
5
5 14 4 10 2
Output
0
2
1
1
3
Note

In the third testcase, you can perform the operation twice with $$$i = 1$$$.

After that, the array is $$$a = [2, 3, 2, 3]$$$, and $$$\max(2, 3, 2, 3) - \min(2, 3, 2, 3) = 3 - 2 = 1$$$.