11013번 - The Missing Permutation 다국어

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 ≤ 10⁵) indicating the length of the permutation. The next line contains a incomplete permutation a₁, a₂, ··· , a_n. If a_i = 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.