브리징 시그널
시간 제한1초메모리 제한128 MB
두 블록의 포트를 잇는 순열이 주어질 때, 교차하지 않는 신호 수를 최대화하려면 최장 증가 부분열을 구해야 합니다.
문제
두 개의 직사각형 블록이 나란히 있고, 각 블록에는 위에서 아래로 1번부터 N번까지 번호가 붙은 포트가 있다. 왼쪽 블록의 i번 포트는 오른쪽 블록의 k_i번 포트와 연결되어야 한다.
서로 다른 두 시그널을 생각해 보자. 왼쪽 블록에서는 한 시그널이 다른 시그널보다 위에 있는데, 오른쪽 블록에서는 그 순서가 뒤바뀐다면 두 시그널은 교차한다. 교차하는 시그널 중 일부는 브리징하여 실리콘 표면 위로 띄울 수 있지만, 브리징해야 하는 시그널 수는 가능하면 적어야 한다.
실리콘 표면 위에서 서로 교차하지 않고 그대로 연결할 수 있는 시그널의 최대 개수를 구하시오.
입력
첫 줄에 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스의 첫 줄에는 포트의 개수 N이 주어진다. (1 ≤ N ≤ 40000)
다음 N개의 줄에는 정수 k_i가 한 줄에 하나씩 주어진다. i번째 정수는 왼쪽 블록의 i번 포트가 연결되어야 하는 오른쪽 블록의 포트 번호이다. (1 ≤ k_i ≤ N)
출력
각 테스트 케이스마다 서로 교차하지 않고 연결할 수 있는 시그널의 최대 개수를 한 줄에 하나씩 출력한다.