← 返回题目列表

AtCoder · arc202_a

A. 合并和增量

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

满足以下条件的整数序列称为 好的序列.

  • 可以执行以下操作 合并操作 零次或多次使序列长度 1.
    • 选择两个连续元素具有相等值的位置。让 x 是这些元素的值。删除两个元素并插入 x+1 位于元素所在的位置。
      例如,如果我们对序列的第二个和第三个元素执行合并操作 (1, 3, 3, 5),操作后的顺序将是 (1, 4, 5).

有一个长度-N 整数序列 A = (A_1, A_2, \dots, A_N).
您可以执行以下操作 插入操作 零次或多次。

  • 选择任意整数 x。插入一个 x 在任何位置 A (可能是开始或结束)。

需要进行的最少插入操作次数是多少 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

对于第一个测试用例,序列 (4, 2, 2, 3) 通过插入获得 3 结束时 A 是一个很好的序列,因为它可以减少长度 1 通过按以下步骤执行合并操作。

  • 删除 2在第二个和第三个位置并插入 2+1=3。序列变为 (4, 3, 3).
  • 删除 3在第二个和第三个位置并插入 3+1=4。序列变为 (4, 4).
  • 删除 4s 在第 1 和第 2 位置并插入 4+1=5。序列变为 (5).

不可能使 A 一个好的序列,插入操作少于一次,所以答案是 1.