Rohit loves to play poker. He has N piles of poker chips in a line. Number of chips in pile i is A[i]. He wants to rearrange them such that the number of chips in pile i is one less than number of chips in pile i+1 for 1<=i<=N-1.

To achieve this,he can take one coin from a pile and place it in another pile.Find the minimum number of coins he has to displace to reach the above configuration.

Input:

First line contains T, the number of test cases.

For each test case, a single integer N is given followed by the N integers representing array A.

Output:

Output a single integer which is the minimum number of coins which need to be displaced.If the configuration cannot be reached print -1.

Constraints:

1<=T<=50

1<=N<=50

1<=A[i]<=50

Sample Input:

3

5

2 3 4 5 1

3

10 10 10

4

3 3 3 3

Sample Output:

4

1

-1