绫的案头有一串长度为 $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
说明
对于第一组数据：
操作次数为 $6$ 的方案如下：
- 将一颗光彩值为 $1$ 的珍珠串入 $b$ 的末尾。
- 将一颗光彩值为 $2$ 的珍珠串入 $b$ 的末尾。
- 将一颗光彩值为 $3$ 的珍珠串入 $b$ 的末尾。
- 将 $b$ 中从头至尾第 $3$ 颗珍珠的光彩值提高 $1$。
- 将一颗光彩值为 $5$ 的珍珠串入 $b$ 的末尾。
- 将一颗光彩值为 $6$ 的珍珠串入 $b$ 的末尾。