Merge and Increment

AtCoder

IDarc202_a

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

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

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 $2$s at the 2nd and 3rd positions and insert $2+1=3$. The sequence becomes $(4, 3, 3)$.
*   Remove the $3$s at the 2nd and 3rd positions and insert $3+1=4$. The sequence becomes $(4, 4)$.
*   Remove the $4$s 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$.

API Response (JSON)

{
  "problem": {
    "name": "Merge and Increment",
    "description": {
      "content": "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 lengt",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc202_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "An integer sequence that satisfies the following condition is called a **good sequence**.\n\n*   It is possible to perform the following **merge operation** zero or more times to make the sequence lengt...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments