AT_arc202_a [ARC202A] Merge and Increment

次の条件を満たす整数列を **良い数列** と呼びます。 - 次の **マージ操作** を $ 0 $ 回以上自由な回数繰り返して、数列の長さを $ 1 $ にすることができる。 - 値の等しい要素が $ 2 $ 個連続している箇所を選ぶ。その要素の値を $ x $ とする。 $ 2 $ 個の要素を両方取り除き、要素があった場所に $ x+1 $ を挿入する。 例えば $ (1, 3, 3, 5) $ という数列の前から $ 2 $ 番目と $ 3 $ 番目の要素を選んでマージ操作を行うと、操作後の数列は $ (1, 4, 5) $ になる。 長さ $ N $ の整数列 $ A = (A_1, A_2, \dots, A_N) $ があります。 あなたは以下の **挿入操作** を $ 0 $ 回以上自由な回数繰り返すことができます。 - 整数 $ x $ を自由に選ぶ。 $ A $ の自由な位置に $ x $ を $ 1 $ 個挿入する。(位置は先頭および末尾でもよい) $ A $ を良い数列にするには最小で何回挿入操作を行う必要がありますか？なお、制約を満たす任意の $ N $ および $ A $ に対して、有限回の挿入操作で $ A $ を良い数列にすることが可能です。 $ T $ 個のテストケースが与えられるので、それぞれについて問題を解いてください。

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

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。 各テストケースでは、 $ A $ を良い数列にするために必要な最小の挿入操作の回数を出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、 $ A $ の末尾に $ 3 $ を挿入してできる数列 $ (4, 2, 2, 3) $ は以下の手順でマージ操作を行うことで数列の長さを $ 1 $ にできるので良い数列です。 - 前から $ 2 $ 番目と $ 3 $ 番目の $ 2 $ を取り除き、 $ 2+1=3 $ を挿入する。数列は $ (4, 3, 3) $ になる。 - 前から $ 2 $ 番目と $ 3 $ 番目の $ 3 $ を取り除き、 $ 3+1=4 $ を挿入する。数列は $ (4, 4) $ になる。 - 前から $ 1 $ 番目と $ 2 $ 番目の $ 4 $ を取り除き、 $ 4+1=5 $ を挿入する。数列は $ (5) $ になる。 $ 1 $ 回未満の挿入操作で $ A $ を良い数列にすることはできないので、答えは $ 1 $ 回です。 ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq 10^9 $ - 全てのテストケースに対する $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力される値は全て整数