← 返回题目列表

AtCoder · abc443_d

D. 典当线

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

分数: 400 点

问题陈述

有一个 N \times N 网格,每列放置一件。
专栏中的作品 i 放置在行中 R_i 从顶部。

您可以执行以下操作零次或多次:

  • 选择一个不在最上面一行的棋子,并将该棋子移动到 位于其正上方的单元格.

找出所有整数满足以下条件所需的最少运算次数 i 满意 1 \le i \le N-1:

  • 让这件作品进入专栏 i 排成一排 x 从顶部和列中的部分 i+1 排成一排 y 从顶部。然后, |x-y| \le 1.

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 所有输入值均为整数。
  • 1 \le T \le 50000
  • 2 \le N \le 3 \times 10^5
  • 1 \le R_i \le N
  • 对于单个输入,总和 N 不超过 3 \times 10^5.

输入

输入由标准输入按以下格式给出:

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

每个测试用例均按以下格式给出:

N
R_1 R_2 \dots R_N

输出

输出 T 行。

的 i- 第行应包含以下问题的答案 i- 第一个测试用例。 总共


示例输入 1

5
5
5 2 1 3 4
2
1 1
3
1 3 1
9
9 9 8 2 4 4 3 5 3
20
7 4 6 2 15 5 17 15 1 8 18 1 5 1 12 11 2 7 8 14

示例输出 1

4
0
1
16
105

此输入包含五个测试用例。

对于第一个测试用例,通过执行如下操作,最少需要四次操作即可满足问题陈述中的条件。

  • 将棋子移动到 5从左侧到其正上方单元格的第列。这些碎片成行 5,2,1,3,3 从左到右。
  • 将棋子移动到 1- 从左侧到其正上方单元格的第 列。这些碎片成行 4,2,1,3,3 从左到右。
  • 将棋子移动到 1- 从左侧到其正上方单元格的第 列。这些碎片成行 3,2,1,3,3 从左到右。
  • 将棋子移动到 4从左侧到其正上方单元格的第列。这些碎片成行 3,2,1,2,3 从左到右。

对于第二个测试用例,无需执行任何操作即可满足条件。