#620 Farewell

Statement

Statement language

There are $N$ integers arranged from left to right in the order $A_1,A_2,\cdots,A_N$ . You may perform the following operation on the sequence.

Choose and delete one element from the current sequence.
Increase the value of every element to the left of the deleted element by $1$ , and decrease the value of every element to its right by $1$ .

The deleted element disappears, and the remaining elements retain their relative order. The changes affect all remaining elements on the corresponding side, not just the adjacent elements, and accumulate across operations.

For example, deleting the middle element $-1$ from $(2,-1,3)$ produces $(3,2)$ . Deleting the rightmost element $2$ next leaves $(4$ .

Repeat the operation until exactly one element remains. Find the maximum possible value of that element.

The initial values, intermediate values, and final value may all be negative. If $N=1$ , no operations are performed and the initial element remains.

Input

The input is given in the following format.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the maximum possible value of the final remaining element on a separate line.

Constraints

$1 \leq T \leq 1\ 000$ .
$1 \leq N \leq 200\ 000$ .
$- 10^{9} \leq$ ().

Subtasks

#	Score	Constraints
1	9	$N \leq 7$ .
2	15	$N \leq 100$ .
3	34	$A_i \geq A_{i+1}$ ().

Samples

Input

4
3
2 -1 3
1
-7
3
0 100 101
4
-5 -5 -5 -5

Output

In the first test case, the deletions described in the statement leave $4$ , and no larger final value is possible.

In the second test case, there is already only one element, so no operations are performed.

In the third test case, deleting the leftmost element $0$ produces $(99,100)$ . Deleting the rightmost element $100$ next leaves $($ , which is the maximum possible value.