调用大小为 $$$m$$$ 的数组 $$$b$$$ 好 如果满足以下条件:
- $$$1 \leq b_i \leq i$$$ 对于每个 $$$1 \leq i \leq m$$$。
- 存在一个大小为 $$$m$$$ 的排列$$$^{\text{∗}}$$$ $$$p$$$,使得对于每个 $$$1 \leq i \leq m$$$,$$$b_i$$$ 是最小整数,其中 $$$\min(p_{b_i}, p_{b_i+1}, \ldots, p_i)=p_i$$$。
例如,数组 $$$[1,1,3,3,5]$$$ 是 好 (其中排列 $$$p=[2,1,5,3,4]$$$ 满足第二个要求),但数组 $$$[1,1,2]$$$ 不满足。
注意空数组被认为是 好.
给你一个大小为 $$$n$$$ 的数组 $$$a$$$。求最长的长度 好 $$$a$$$ 的子序列$$$^{\text{†}}$$$。
$$$^{\text{*}}$$$长度$$$m$$$的排列是一个由从$$$1$$$到$$$m$$$以任意顺序的$$$m$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$m=3$$$但数组中有$$$4$$$)。
$$$^{\text{†}}$$$ 序列 $$$c$$$ 是序列 $$$d$$$ 的子序列,如果 $$$c$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$d$$$ 获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 15\,000$$$) – $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$) — 表示数组 $$$a$$$。
保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$15\,000^2$$$。
输出
对于每个测试用例,在新行上输出 $$$a$$$ 的最长好子序列的长度。
示例
输入复制
551 1 3 3 531 1 242 2 2 271 2 4 2 4 6 211
输出复制
5 2 0 5 1
注意
在第一个测试用例中,整个序列是 好.
在第二个测试用例中,最长的 好 子序列是 $$$[1,2]$$$。