問題文

数直線上に $N$ 頭の馬がいる. これらの馬は $1,2, \dots, N$ と番号が付けられている.

最初, 馬 $i$ は座標 $A_i$ にいる.

チェリーちゃんが笛を鳴らすと, $N$ 頭の馬は同時に以下の行動を行う.

• 笛が鳴ったとき, 馬 $i$ が座標 $x$ にいるとする. このとき, 馬 $i$ は座標 $(x+i)$ に移動する.

チェリーちゃんが $0$ 回以上の任意の回数だけ笛を鳴らすとき, 以下を満たすようなことはあり得るか? あり得るならば, そのような状況になるまでにチェリーちゃんが鳴らす笛の回数の最小値を求めよ.

• 馬 $i$ がいる座標を $X_i$ とする. このとき, $X_1 \lt X_2 \lt \dots \lt X_{N-1} \lt X_N$ を満たす.

制約

• $1 \leq T \leq 10^5$.
• 各テストケースに対する制約.
  • $2 \leq N \leq 2 \times 10^5$.
  • $0 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)$.
• テストファイルに対する制約.
  • $T$ 個のテストケースにおける $N$ の総和は $2 \times 10^5$ 以下である.
• 入力は全て整数である.

入力

$T$
${\rm Testcase}_1$
${\rm Testcase}_2$
$\vdots$
${\rm Testcase}_T$

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

出力

出力は $T$ 行からなる. 第 $t~(1 \leq t \leq T)$ 行目には, 第 $t$ テストケースに対する解答を以下の形式で出力せよ.

• いくら笛を鳴らしても条件を満たさないならば, -1 を出力せよ. 存在するならば, 条件を満たすまでに笛を鳴らす回数の最小値を整数で出力せよ.

最後に改行も忘れないこと.

サンプル

4
3
3 1 2
5
1 2 3 4 5
4
46 46 46 46
10
886822852 554802233 259460418 345136263 8466085 424914285 852474622 856826548 201867 777749594

3
0
1
856624682