CF2124H Longest Good Subsequence

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.

Each 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.

For each test case, output the length of the longest good subsequence of $ a $ on a new line.

In the first test case, the entire sequence is good. In the second test case, the longest good subsequence is $ [1,2] $ .