分数: 700 点
问题陈述
满足以下条件的整数序列称为 好的序列.
- 可以执行以下操作 合并操作 零次或多次使序列长度 1.
- 选择两个连续元素具有相等值的位置。让 x 是这些元素的值。删除两个元素并插入 x+1 位于元素所在的位置。
例如,如果我们对序列的第二个和第三个元素执行合并操作 (1, 3, 3, 5),操作后的顺序将是 (1, 4, 5).
- 选择两个连续元素具有相等值的位置。让 x 是这些元素的值。删除两个元素并插入 x+1 位于元素所在的位置。
有一个长度-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.