반도체 설계
시간 제한2초메모리 제한128 MB
포트 연결을 나타내는 순열이 주어질 때, 선이 교차하지 않도록 최장 증가 부분수열의 길이를 구합니다.
문제
반도체를 설계할 때 한쪽의 n개 포트를 반대쪽의 n개 포트와 연결해야 하는 경우가 있다. 왼쪽의 i번 포트가 연결되어야 하는 오른쪽 포트 번호가 주어진다.
일부 연결만 선택할 수 있으며, 선택한 연결선끼리는 서로 교차하면 안 된다. 교차하지 않게 선택할 수 있는 연결의 최대 개수를 구하라.
입력
첫째 줄에 정수 n (1 <= n <= 40,000)이 주어진다.
둘째 줄에는 n개의 정수가 주어진다. i번째 정수는 왼쪽 i번 포트와 연결되어야 하는 오른쪽 포트 번호이다. 각 정수는 1 이상 n 이하이며, 같은 번호는 두 번 나타나지 않는다.
출력
교차하지 않게 선택할 수 있는 연결의 최대 개수를 출력한다.