我们定义 块 是一个数组,其中的所有元素都等于数组的长度。例如,$$$[3, 3, 3]$$$、$$$[1]$$$ 和 $$$[4, 4, 4, 4]$$$ 是 块,而 $$$[1, 1, 1]$$$ 和 $$$[2, 3, 3]$$$ 则不是。
调用一个数组 整洁 如果可以通过任意数量的串联获得 块 (可能为零)。请注意,空数组始终是 整洁.
给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。求最长的长度 整洁 子序列$$$^{\text{*}}$$$。
$$$^{\text{*}}$$$ 序列 $$$c$$$ 是序列 $$$a$$$ 的子序列,如果 $$$c$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$a$$$ 获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 最长的长度 整洁 $$$a$$$ 的子序列。
示例
输入复制
61122 242 2 1 161 2 3 3 3 188 8 8 8 8 8 8 7102 3 3 1 2 3 5 1 1 7
输出复制
1 2 4 5 0 5
注意
在第一个测试用例中,整个数组 $$$[1]$$$ 是 整洁 因为它是 块.
在第二个测试用例中,整个数组 $$$[2, 2]$$$ 是 整洁 因为它是 块.
在第三个测试用例中,整个数组 $$$[2,2,1,1]$$$ 是 整洁 因为它是三个的串联 块:$$$[2,2]$$$、$$$[1]$$$ 和 $$$[1]$$$。
在第四个测试用例中,最长的测试用例之一 $$$a$$$ 的 整洁 子序列是 $$$[1, 3, 3, 3, 1]$$$。
在第五个测试用例中,最长的 $$$a$$$ 的 整洁 子序列是空子序列。