A - Merge and Increment Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

次の条件を満たす整数列を 良い数列 と呼びます。

  • 次の マージ操作 を 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 個のテストケースが与えられるので、それぞれについて問題を解いてください。

制約

  • 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 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。ここで \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 を良い数列にするために必要な最小の挿入操作の回数を出力せよ。

入力例 1

4
3
4 2 2
1
1
5
1 3 5 4 2
10
766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 122410709 549392045

出力例 1

1
0
6
1889132222

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 回です。

Score : 700 points

Problem Statement

An integer sequence that satisfies the following condition is called a good sequence.

  • It is possible to perform the following merge operation zero or more times to make the sequence length 1.
    • Choose a location where two consecutive elements have equal values. Let x be the value of those elements. Remove both elements and insert x+1 at the location where the elements were.
      For example, if we perform a merge operation on the 2nd and 3rd elements of the sequence (1, 3, 3, 5), the sequence after the operation will be (1, 4, 5).

There is a length-N integer sequence A = (A_1, A_2, \dots, A_N).
You can perform the following insertion operation zero or more times.

  • Choose any integer x. Insert one x at any position in A (possibly the beginning or end).

What is the minimum number of insertion operations needed to make A a good sequence? For any N and A satisfying the constraints, it is possible to make A a good sequence with a finite number of insertion operations.

You are given T test cases; solve the problem for each of them.

Constraints

  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • The sum of N over all test cases is at most 2 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format. Here, \mathrm{case}_i means the i-th test case.

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
A_1 A_2 \dots A_N

Output

Output T lines. The i-th line should contain the answer for the i-th test case.
For each test case, output the minimum number of insertion operations needed to make A a good sequence.

Sample Input 1

4
3
4 2 2
1
1
5
1 3 5 4 2
10
766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 122410709 549392045

Sample Output 1

1
0
6
1889132222

For the 1st test case, the sequence (4, 2, 2, 3) obtained by inserting 3 at the end of A is a good sequence because it can be reduced to length 1 by performing merge operations in the following steps.

  • Remove the 2s at the 2nd and 3rd positions and insert 2+1=3. The sequence becomes (4, 3, 3).
  • Remove the 3s at the 2nd and 3rd positions and insert 3+1=4. The sequence becomes (4, 4).
  • Remove the 4s at the 1st and 2nd positions and insert 4+1=5. The sequence becomes (5).

It is impossible to make A a good sequence with fewer than one insertion operation, so the answer is 1.