1624번 - 데크 소트

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

N개의 수가 주어졌을 때, 첫 번째 수부터 마지막 수까지 순서대로 아래 세 가지 중에 한 방법을 이용해 데크에 넣어야 한다.

1. 수를 존재하는 데크중 하나의 맨 앞에 넣는다.
2. 수를 존재하는 데크중 하나의 맨 뒤에 넣는다.
3. 새로운 데크를 만들어서 그 곳에 수를 넣는다.

위의 방법을 이용해서 모든 수를 적절히 데크에 넣은 다음, 모든 데크를 적절히 이어 붙여 오름차순으로 만들려고 한다. 이때, 필요한 데크 개수의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 수의 개수 N이 주어진다. N은 1,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 한 줄에 하나씩 주어진다. 각 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 수가 중복될 수도 있다.

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