AT_bogosortcontest_div2_b Erase Mountain

長さ $ 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 $ 個のテストケースについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

各テストケースについて、答えを整数として出力せよ。

### Sample Explanation 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 $ が答えとなります。 ### Constraints - $ 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 $ 以下 - 入力される数値はすべて整数