艾伦·图灵站在一条带子上,带子被分成两个方向无限的单元。
单元格从左到右用连续整数编号。艾伦最初站在牢房 $$$0$$$ 中。每个单元格 $$$x$$$ 的左侧单元格为 $$$x - 1$$$,右侧单元格为 $$$x + 1$$$。
每个单元格可以包含整数或为空。最初所有单元格都是空的。
艾伦被赋予从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$a_1, a_2, \ldots, a_n$$$,该排列是在所有长度为 $$$n$$$ 的排列中均匀随机选择的。
在$$$1$$$时刻,整数$$$a_1$$$被写入Alan所在的单元格$$$0$$$中。
从 $$$2$$$ 到 $$$n$$$(含)的每次 $$$i$$$ 都会发生以下情况。首先,艾伦决定是留在他当前所在的同一个单元格中,还是移动到左侧的相邻单元格,或者移动到右侧的相邻单元格。之后,将整数$$$a_i$$$写入Alan所在的单元格中。如果该单元格已经包含某个整数,则旧整数将被覆盖并且从那时起不再相关。
一旦$$$a_n$$$在时间$$$n$$$被写入某个单元格,则从左到右形成单元格中包含的所有整数的序列$$$b$$$。空单元格将被忽略。
图灵的奖励等于序列$$$b$$$的最长递增子序列的长度。
帮助艾伦并确定如果他表现最佳,他的奖励的最大可能价值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例都以两行给出。每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 15\,000$$$) - 给予艾伦的排列的长度。
第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - 排列的元素。
保证在相应长度的所有排列中均匀随机选择排列。
所有测试用例的 $$$n$$$ 总和不超过 $$$15\,000$$$。
输出
对于每个测试用例,输出一个整数——图灵奖的最大可能值。
不允许黑客解决此问题。
示例
输入 #1
4 2 1 2 4 4 1 2 3 7 3 6 5 7 4 1 2 7 5 2 3 7 6 1 4
输出 #1
2 3 4 4
注意
序列 $$$b$$$ 的最长递增子序列是可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得的最长递增序列。
在第一个测试用例中,Alan 只能在时间 $$$2$$$ 时做出决定。如果 Alan 留在单元格 $$$0$$$ 中,则序列 $$$b$$$ 将等于 $$$[2]$$$。如果 Alan 向左移动到单元格 $$$-1$$$,则序列 $$$b$$$ 将等于 $$$[2, 1]$$$。如果 Alan 向右移动到单元格 $$$1$$$,则序列 $$$b$$$ 将等于 $$$[1, 2]$$$。仅在最后一种情况下,$$$b$$$ 的最长递增子序列的长度为$$$2$$$,因此,答案等于$$$2$$$。
在第二个测试用例中,最佳操作序列之一如下所示:在 $$$2$$$ 和 $$$3$$$ 时刻向左移动,在 $$$4$$$ 时刻向右移动。那么序列$$$b$$$将等于$$$[2, 3, 4]$$$,并且其最长递增子序列的长度为$$$3$$$。
在第三个测试用例中,最好的方法之一是始终向左移动。那么序列$$$b$$$将等于$$$[2, 1, 4, 7, 5, 6, 3]$$$,并且其最长递增子序列的长度为$$$4$$$。
在第四个测试用例中,最好的方法之一是向右移动四次,然后向左移动一次,并在同一单元格中停留一次。序列 $$$b$$$ 将等于 $$$[5, 2, 3, 4, 6]$$$。