The Missing Permutation

Interview

Time limit15sMemory limit256 MB

Summary

Fill the zeros with the missing values to maximize the length of the longest increasing subsequence.

Level: Medium5 of 10
Topics: Greedy, Dynamic programming, Binary search
Solved: No attempts yet

Problem

Little Tomato keeps a permutation $P$ of the numbers $1$ through $n$ on a board. Every day he swaps a few numbers of $P$ to get a new permutation $P'$ , then looks for the longest increasing subsequence (LIS) of $P'$ . He believes that he will eventually find a faster way to compute an LIS.

One day an earthquake shook some of the numbers off the board. Every fallen number goes back into an empty slot, and Tomato picks which slot each one lands in. How long can the LIS of the restored permutation be?

An increasing subsequence is a subsequence whose values grow from left to right.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 100$ ).

Each test case starts with a line holding the length $n$ of the permutation ( $1 \le n \le 10^5$ ). The next line holds the incomplete permutation $a_1, a_2, \dots, a_n$ . If $a_i = 0$ , the number that sat at position $i$ has fallen off.

The input is always valid. The nonzero values are distinct and lie between $1$ and $n$ , and the fallen numbers are exactly the values of $1$ through $n$ that do not appear. The whole input is smaller than 10MB.

Output

For each test case, print the largest possible length of the LIS of the restored permutation on its own line.

Examples3

Example 1

Input

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

Expected output

Example 2
Input
```
2
1
0
1
1
```
Expected output
```
1
1
```

Example 3

Input

3
5
1 2 3 4 5
5
5 4 3 2 1
8
3 1 4 7 2 6 5 8

Expected output

5
1
4