文理学院程序设计在线练习


Step By Step

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 33   Accepted Submission(s): 12
Problem Description

Recently, Tony Lang has been working on a way to pour wine:”Step By Step”.
There are n glasses of wine, numbered from 1 to n. In this way, the volume of wine is increasing, which means the wine in i+1th glass must be more than ith. However, Tony is unable to do it. Luckily, he can choose some glasses, and pour a part of wine into others, so that achieve the same effect. Meanwhile, he can also drink the rest of the wine.
Note: the capacity of the glasses can be seen as infinite, and the number of wine added and drunk is integer.
Tony wants to drink the most wine on the premise of "step by step".

Input

The first line of data is the number of cases T.
Within each case data :
The first line is an integers n, which represents the number of glasses
The second line contains n integers a1,a2,a3,...,an.
ai means the volume of wine in ith glass.
T <= 100 1<=n<=100000 1<=ai<=1000000000

Output

One line for each case, output the maximum amount of wine Tony can drink. If there is no way to meet the requirements of ”Step By Step”, please output -1.
The data guarantees that there is only one solution.

Sample Input
2
2
3 2
3
1 1 1
Sample Output
2
-1
Hint

The amount of data is huge, please use scanf.

Source

2019绍兴联赛