데크 소트

데크는 앞과 뒤 양쪽에서 원소를 넣거나 뺄 수 있는 자료구조이다.

정수 N개가 순서대로 주어진다. 각 정수는 입력된 순서를 지켜 다음 세 가지 방법 중 하나로 데크들에 넣어야 한다.

1. 이미 있는 데크 하나의 맨 앞에 넣는다.
2. 이미 있는 데크 하나의 맨 뒤에 넣는다.
3. 새 데크를 만들고 그 데크에 넣는다.

모든 정수를 넣은 뒤, 만들어진 데크들을 어떤 순서로 이어 붙였을 때 전체 수열이 오름차순(비내림차순)이 되도록 하려고 한다. 필요한 데크 수의 최솟값을 구하시오.

첫째 줄에 수의 개수 N이 주어진다. N은 1,000 이하의 자연수이다.

다음 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 각 정수는 -1,000 이상 1,000 이하이며, 같은 수가 여러 번 나올 수 있다.

데크들을 이어 붙여 오름차순으로 만들기 위해 필요한 데크 수의 최솟값을 첫째 줄에 출력한다.