H. Longest Good Subsequencetime limit per test7 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output Call an array $$$b$$$ of size $$$m$$$ good if the following conditions hold: $$$1 \leq b_i \leq i$$$ for each $$$1 \leq i \leq m$$$. There exists a permutation$$$^{\text{∗}}$$$ $$$p$$$ of size $$$m$$$ such that for each $$$1 \leq i \leq m$$$, $$$b_i$$$ is the smallest integer where $$$\min(p_{b_i}, p_{b_i+1}, \ldots, p_i)=p_i$$$. For example, the array $$$[1,1,3,3,5]$$$ is good (where the permutation $$$p=[2,1,5,3,4]$$$ satisfies the second requirement), but the array $$$[1,1,2]$$$ isn't.Note the empty array is considered to be good.You are given an array $$$a$$$ of size $$$n$$$. Find the length of the longest good subsequence$$$^{\text{†}}$$$ of $$$a$$$.$$$^{\text{∗}}$$$A permutation of length $$$m$$$ is an array consisting of $$$m$$$ distinct integers from $$$1$$$ to $$$m$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$m=3$$$ but there is $$$4$$$ in the array). $$$^{\text{†}}$$$A sequence $$$c$$$ is a subsequence of a sequence $$$d$$$ if $$$c$$$ can be obtained from $$$d$$$ by the deletion of several (possibly, zero or all) element from arbitrary positions. InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 15\,000$$$) – the length of $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$) — denoting the array $$$a$$$.It is guaranteed that the sum of $$$n^2$$$ does not exceed $$$15\,000^2$$$ over all test cases.OutputFor each test case, output the length of the longest good subsequence of $$$a$$$ on a new line.ExampleInput551 1 3 3 531 1 242 2 2 271 2 4 2 4 6 211Output5
2
0
5
1
NoteIn the first test case, the entire sequence is good.In the second test case, the longest good subsequence is $$$[1,2]$$$.