Ling has a pearl necklace $a$ of length $n$ on her desk. Each pearl has a luster value, and the luster value of the $i$-th pearl from the beginning to the end is $a_i$.

Ling holds a pearl necklace $b$, which is initially empty. She performs several operations on this necklace. In each operation, she can choose one of the following two options:

• Add a pearl with a luster value of $i$ to the end of $b$.
• Increase the luster value of any pearl in $b$ by $1$.

Ling wants to know: what is the minimum number of operations required to make the pearl necklace $b$ identical to $a$? If it is impossible to make $b$ identical to $a$, output -1.

Input

The input contains multiple test cases. The first line contains a single positive integer $T$ ($1 \le T \le 10^4$), representing the number of test cases.

For each test case: The first line contains a single positive integer $n$ ($1 \le n \le 5 \times 10^5$), representing the length of the pearl necklace $a$. The second line contains $n$ positive integers, where the $i$-th positive integer is $a_i$ ($1 \le a_i \le 10^{12}$), representing the luster value of the $i$-th pearl in $a$ from beginning to end.

It is guaranteed that the sum of $n$ over all $T$ test cases does not exceed $5 \times 10^5$.

Output

For each test case: Output a single integer representing the minimum number of operations. If it is impossible to make $b$ identical to $a$, output -1.

Examples

Input 1

3
5
1 2 4 5 6
8
1 2 4 5 5 8 10 9
3
3 2 1

Output 1

6
13
-1

Note

For the first test case: A sequence of 6 operations is as follows: 1. Add a pearl with a luster value of 1 to the end of $b$. 2. Add a pearl with a luster value of 2 to the end of $b$. 3. Add a pearl with a luster value of 3 to the end of $b$. 4. Increase the luster value of the 3rd pearl in $b$ (from beginning to end) by 1. 5. Add a pearl with a luster value of 5 to the end of $b$. 6. Add a pearl with a luster value of 6 to the end of $b$.