교원이는 친구들과 카드게임을 즐겨한다. 카드게임의 규칙은 다음과 같다.
|
1. 게임 시작 시, 1명당 총 n장의 숫자 카드를 받는다.
2. 카드는 반드시 받은 순서대로 왼쪽부터 바닥에 놓는다.
3. 자신의 차례가 왔을 때 자신의 카드 중 1장을 버릴 수 있다.
4. 자신의 남은 카드가 가장 먼저 오름차순이 되면 게임의 승자가 된다.
(단, 남은 카드에 같은 숫자가 있어서는 안 된다.)
|
교원이가 받은 숫자 카드가 순서대로 주어졌을 때, 교원이가 버려야하는 카드의 최소 개수를 계산하는 프로그램을 작성하시오.
예를 들어, 받은 숫자 카드가 1, 3, 2, 9, 7, 8, 5, 10 일 때, 게임의 승자가 되려면 3, 9, 5를 버리거나 2, 9, 7, 8을 버리는 등 여러 가지 방법이 있으므로 버려야하는 카드의 최소 개수는 3이다.
입력예시1)
8
1 3 2 9 7 8 5 10
출력예시1)
3