綾的案頭有一串長度為 $n$ 的珍珠鏈 $a$，每顆珍珠有其光彩值，從頭至尾第 $i$ 顆珍珠的光彩值為 $a_i$。
綾手中懸著一串珍珠鏈 $b$，初始為空。她對這個珍珠鏈進行若干次操作，第 $i$ 次操作可從以下兩種操作中選擇其中一種：
- 將一顆光彩值為 $i$ 的珍珠串入 $b$ 的末尾。
- 將 $b$ 中任意一顆珍珠的光彩值提高 $1$。
綾想要知道：至少需要多少次操作，才能使得珍珠鏈 $b$ 與 $a$ 完全相同？若無法使得珍珠鏈 $b$ 與 $a$ 完全相同，回答 $-1$ 即可。
輸入格式
本題有多組數據。第一行一個正整數 $T$ ($1 \le T \le 10^4$)，表示數據組數。
對於每組數據： 第一行一個正整數 $n$ ($1 \le n \le 5 \times 10^5$)，表示珍珠鏈 $a$ 的長度。 第二行 $n$ 個正整數，第 $i$ 個正整數為 $a_i$ ($1 \le a_i \le 10^{12}$)，表示 $a$ 中從頭至尾第 $i$ 顆珍珠的光彩值。
保證 $T$ 組數據中 $n$ 的和不超過 $5 \times 10^5$。
輸出格式
對於每組數據： 輸出一行一個整數，表示最少操作次數，若無法使得珍珠鏈 $b$ 與 $a$ 完全相同，輸出 $-1$。
範例
輸入 1
3 5 1 2 4 5 6 8 1 2 4 5 5 8 10 9 3 3 2 1
輸出 1
6 13 -1
說明 1
對於第一組數據： 操作次數為 $6$ 的方案如下：
- 將一顆光彩值為 $1$ 的珍珠串入 $b$ 的末尾。
- 將一顆光彩值為 $2$ 的珍珠串入 $b$ 的末尾。
- 將一顆光彩值為 $3$ 的珍珠串入 $b$ 的末尾。
- 將 $b$ 中從頭至尾第 $3$ 顆珍珠的光彩值提高 $1$。
- 將一顆光彩值為 $5$ 的珍珠串入 $b$ 的末尾。
- 將一顆光彩值為 $6$ 的珍珠串入 $b$ 的末尾。