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