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".

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

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.