| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 15 초 | 256 MB | 44 | 7 | 5 | 31.250% |
Little Tomato has a permutation P from 1 to n on a board. Each day, he swaps some numbers in P to form a new permutation P', and then tries to find the longest increasing subsequence (LIS) of P'. He believes that he can eventually find a faster algorithm for calculating LIS.
One day after an earthquake, some of the numbers in the permutation P has dropped off the board. Little tomato soon wondered, if he puts all the numbers back in a certain way, what will be the largest possible length of the LIS of the recovered permutation?
First line of the input contains an integer T (1 ≤ T ≤ 100) denoting the number of the test cases. For each test case, the first line contains an integer n (1 ≤ n ≤ 105) indicating the length of the permutation. The next line contains a incomplete permutation a1, a2, ··· , an. If ai = 0, that means the number originally at the i-th position has dropped. The input will be always valid, and less than 10MB.
For each test case, output the maximum possible length of the LIS of the recovered permutation.
4 5 0 0 0 0 0 10 1 2 3 4 0 0 0 0 9 10 14 1 0 3 0 5 0 7 0 9 0 11 0 13 0 9 3 0 0 0 7 8 9 0 0
5 10 14 7
ICPC > Regionals > Asia Pacific > Taiwan > Taiwan Online Programming Contest > TOPC 2015 H번