問題文

長さ N の正整数列 A_1, A_2, \dots, A_N が与えられます。

この数列に対して、以下の操作を何回でも（0 回でもよい）行うことができます。

• A_{i-1} \leq A_{i} かつ A_{i} \geq A_{i + 1} を満たす i \ (2 \leq i \leq N - 1) を選び A_{i} を 1 減らす。

A を単調非減少にするための操作回数の最小値を求めてください。どのように操作をしても単調非減少にできない場合は -1 を出力してください。

T 個のテストケースについて答えてください。

制約

• 1 \leq T \leq 10^4
• 3 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• すべてのテストケースについての N の総和は 2\times 10^5 以下
• 入力される数値はすべて整数

入力例 1

3
4
1 4 3 2
5
1 2 3 4 5
3
2 3 1

出力例 1

3
0
-1

1 個目のテストケースについて、

• 1 回目の操作で i = 2 を選ぶと、 A = (1, 3, 3, 2) となります。
• 2 回目の操作で i = 2 を選ぶと、 A = (1, 2, 3, 2) となります。
• 3 回目の操作で i = 3 を選ぶと、 A = (1, 2, 2, 2) となり、単調非減少にすることができます。

2 回以下の操作で A を単調非減少にすることはできないので、 3 が答えとなります。

2 個目のテストケースについて、はじめから A が単調非減少なので 0 が答えとなります。