Bridging Signals

Time limit1sMemory limit128 MB

Summary
Given a permutation of wire connections between two ports, find the longest increasing subsequence to maximize non-crossing signals.
Level

Medium4 of 10

Topics
Binary search, Dynamic programming, Array
Solved
No attempts yet

Problem

Two rectangular blocks are placed side by side. Each block has ports numbered from 1 to N from top to bottom. Port i on the left block must be connected to port k_i on the right block.

Consider two different signals. If one signal starts above the other on the left block but ends below it on the right block, the two signals cross. Some crossing signals can be bridged so that they are lifted above the silicon surface, but as few signals as possible should be bridged.

Find the maximum number of signals that can be connected on the silicon surface without crossing each other.

Input

The first line contains the number of test cases T.

For each test case, the first line contains the number of ports N. (1 ≤ N ≤ 40000)

The next N lines each contain one integer k_i. The i-th integer is the right-block port number that must be connected to port i on the left block. (1 ≤ k_i ≤ N)

Output

For each test case, output one line containing the maximum number of signals that can be connected without crossing.

Examples1

  1. Example 1

    Input
    3
6
4
2
6
3
1
5
10
2
3
4
5
6
7
8
9
10
1
9
5
8
9
2
3
1
7
4
6
    Expected output
    3
9
4