← 返回题目列表

Codeforces · 1637/H

H. 最小化反转次数

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

给你一个长度为 $$$n$$$ 的排列 $$$p$$$。

您可以选择任何子序列,将其从排列中删除,然后将其插入排列的开头并保持相同的顺序。

对于从 $$$0$$$ 到 $$$n$$$ 的每个 $$$k$$$,在选择长度恰好为 $$$k$$$ 的子序列后,找到排列中可能的最小反转数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 50\,000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 排列的长度。

每个测试用例的第二行包含排列 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$)。

保证$$$n$$$的总和不超过$$$5 \cdot 10^5$$$。

输出

对于每个测试用例输出 $$$n + 1$$$ 整数。其中第 $$$i$$$ 必须是 $$$i - 1$$$ 子序列长度的答案。

示例

输入 #1

3
1
1
4
4 2 1 3
5
5 1 3 2 4

输出 #1

0 0
4 2 2 1 4
5 4 2 2 1 5

注意

在第二个测试用例中:

- 对于长度 $$$0$$$:$$$[4, 2, 1, 3] \rightarrow [4, 2, 1, 3]$$$:$$$4$$$ 反转。
- 对于长度 $$$1$$$:$$$[4, 2, \mathbf{1}, 3] \rightarrow [1, 4, 2, 3]$$$:$$$2$$$ 反转。
- 对于长度 $$$2$$$:$$$[4, \mathbf{2}, \mathbf{1}, 3] \rightarrow [2, 1, 4, 3]$$$,或 $$$[4, 2, \mathbf{1}, \textbf{3}] \rightarrow [1, 3, 4, 2]$$$: $$$2$$$ 反转。
- 对于长度 $$$3$$$:$$$[4, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [2, 1, 3, 4]$$$:$$$1$$$ 反转。
- 对于长度 $$$4$$$:$$$[\mathbf{4}, \mathbf{2}, \mathbf{1}, \mathbf{3}] \rightarrow [4, 2, 1, 3]$$$:$$$4$$$ 反转。