给你一个长度为 $$$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$$$ 反转。