分数: 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 从左到右。
对于第二个测试用例,无需执行任何操作即可满足条件。