시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 114 12 10 25.641%

문제

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

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

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

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

입력

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

출력

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

예제 입력

6
3
6
0
9
5
4

예제 출력

2

힌트

  • 새로운 데크를 만든다. Deque1 : {3}
  • 새로운 데크를 만든다. Deque2 : {6}
  • 0을 Deque1의 앞에 넣는다. : {0, 3}
  • 9를 Deque2의 뒤에 넣는다. : {6, 9}
  • 5를 Deque2의 앞에 넣는다. : {5, 6, 9}
  • 4를 Deque2의 앞에 넣는다. : {4, 5, 6, 9}
  • Deque1의 뒤에 Deque2를 붙이면 정렬된다.

출처