园艺师

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　花园的一排景观小树共有 \(n\) 棵，从左到右编号 \(1..n\)，高度分别为 \(h_1,h_2,…,h_n\)。为了美观，需要把这些小树修剪成一样的高度。

　　园艺师老H有一把智能剪刀，一次修剪可以把两棵相邻的小树高度减少 1。那么他最少需要修剪多少次才能达到目标？

【输入格式】

　　输入的第一行包含 \(m（1≤m≤100）\)，表示有 \(m\) 组数据。
　　每组数据包含两行。第一行包含 \(n\)，第二行包含 \(h_1,h_2,…,h_n\)。输入保证所有组数据的 \(n\) 之和不超过 \(10^6\)。

【输出格式】

　　输出 \(m\) 行，每组数据输出一行，表示对用组的答案，若不能达到目标，则输出 -1。

【输入输出样例】

　Input

4
3
7 9 5
6
6 8 6 6 8 6
3
0 1 0
3
10 9 9

　Output

6
8
-1
-1

【样例解释】

　　对于第一组数据，小树 2 和 3 一起修剪两次，然后小树 1 和 2 一起修剪四次，使得所有小树的高度均为 3。
　　对于第二组数据，小树 1 和 2 一起修剪两次，小树 2 和 3 一起修剪两次，小树 4 和 5 一起修剪两次，小树 5 和 6 各一起修剪两次，使得所有小树的高度均为 4。

【数据限制】

　　测试点 2 的所有组数据满足 \(n≤3\) 以及 \(h_i≤100\)。
　　测试点 3-8 的所有组数据满足 \(n≤100\) 以及 \(h_i≤100\)。
　　测试点 9-14 的所有组数据满足 \(n≤100\) 以及 \(0≤h_i≤10^9\)。
　　测试点 15 满足 \(1≤n≤10^5\) 以及 \(0≤h_i≤10^9\)。
　　此外，测试点 3-5 和 9-11 中的 \(n\) 均为偶数，测试点 6-8 和 12-14 中的 \(n\) 均为奇数。

【来源】

　　Mr.he