데크 소트 2

데크는 큐와 비슷하지만 앞과 뒤 양쪽에서 자료를 넣고 뺄 수 있는 자료구조이다.

$N$개의 수가 주어진다. 첫 번째 수부터 마지막 수까지 순서대로 다음 세 가지 중 하나를 골라 처리해야 한다.

1. 이미 만들어 둔 데크 중 하나를 골라 그 맨 앞에 수를 넣는다.
2. 이미 만들어 둔 데크 중 하나를 골라 그 맨 뒤에 수를 넣는다.
3. 데크를 새로 만들고 그곳에 수를 넣는다.

모든 수를 이렇게 넣은 다음, 데크를 원하는 순서로 이어 붙여 전체가 오름차순이 되도록 만들려고 한다. 데크 안의 수는 맨 앞에서 맨 뒤로 읽은 순서 그대로 쓴다. 이때 필요한 데크 개수의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 수의 개수 $N$이 주어진다. $N$은 50보다 작거나 같은 자연수이다. 둘째 줄부터 $N$개의 줄에 수가 한 줄에 하나씩 주어진다. 각 수는 -1000보다 크거나 같고 1000보다 작거나 같은 정수이며, 같은 수가 두 번 주어지지 않는다.

첫째 줄에 필요한 데크의 최소 개수를 출력한다.

수가 3, 6, 0, 9, 5, 4 순서로 주어지면 데크 두 개면 충분하다.

• 데크를 새로 만들어 3을 넣는다. Deque1: {3}
• 데크를 새로 만들어 6을 넣는다. Deque2: {6}
• 0을 Deque1의 맨 앞에 넣는다. Deque1: {0, 3}
• 9를 Deque2의 맨 뒤에 넣는다. Deque2: {6, 9}
• 5를 Deque2의 맨 앞에 넣는다. Deque2: {5, 6, 9}
• 4를 Deque2의 맨 앞에 넣는다. Deque2: {4, 5, 6, 9}
• Deque1 뒤에 Deque2를 이어 붙이면 0, 3, 4, 5, 6, 9가 되어 오름차순이다.