綾の机の上には長さ $n$ の真珠のネックレス $a$ があり、各真珠には光彩値が設定されています。先頭から数えて $i$ 番目の真珠の光彩値は $a_i$ です。

綾は手元に空の真珠のネックレス $b$ を持っています。彼女はこのネックレスに対していくつかの操作を行うことができ、各操作において以下のいずれかを選択できます。

• 光彩値が $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$ 番目の真珠の光彩値を表します。

すべてのテストケースにおける $n$ の合計は $5 \times 10^5$ を超えないことが保証されます。

出力

各テストケースについて、最小の操作回数を 1 行で出力してください。もし $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. 光彩値 1 の真珠を $b$ の末尾に追加する。
2. 光彩値 2 の真珠を $b$ の末尾に追加する。
3. 光彩値 3 の真珠を $b$ の末尾に追加する。
4. $b$ の先頭から 3 番目の真珠の光彩値を 1 増加させる。
5. 光彩値 5 の真珠を $b$ の末尾に追加する。
6. 光彩値 6 の真珠を $b$ の末尾に追加する。