AI 아마겟돈

면접 대비

시간 제한1초메모리 제한2048 MB

요약

티셔츠가 도착하는 순서를 보고, 스크립트가 놓인 더미에 티셔츠가 들어올 때 옮겨야 하는 최소 횟수를 구합니다.

난이도: 보통10점 중 5점
유형: 그리디, 배열, 해시맵
정답자: 아직 제출이 없습니다

문제

인공지능이 정보학자와 수학자의 일을 모두 맡게 된 뒤, 스테판은 가족을 부양하려고 옷가게에 취직했다.

어느 날 스테판은 새로 들어온 티셔츠를 이미 있는 더미 위에 올리는 일을 맡았다. 가게에는 $K$ 종류의 티셔츠가 있으므로 더미도 $K$ 개다. 스테판은 총 $N$ 장의 티셔츠를 한 장씩 받아, 각 티셔츠를 그 종류에 맞는 더미에 올린다.

스테판은 아직도 문제가 가득한 수학 스크립트를 들고 다닌다. 언젠가 자신의 실력이 다시 쓸모 있을 날이 올 것이라 믿기 때문이다. 다만 스크립트를 바닥에 두면 더러워지므로, 스테판은 스크립트를 더미 중 하나 위에 둔다.

스크립트가 놓인 더미에 티셔츠를 올려야 할 때마다, 스테판은 스크립트를 다른 더미로 옮겨야 한다.

스크립트를 계속 옮기느라 스테판은 지쳐 간다. 그는 이런 생각을 멈출 수 없다. "티셔츠가 들어오는 순서를 미리 알면 스크립트를 덜 옮길 텐데." 스테판이 이 문제를 풀도록 도와줄 수 있겠는가?

입력

첫 줄에 자연수 두 개가 주어진다. 티셔츠의 개수 $N$ ( $1 \leq N \leq 10^6$ )과 더미의 개수 $K$ ( $2 \leq K \leq 10^9$ )이다.

이어지는 $N$ 개의 줄에는 각각 자연수 $a_i$ ( $1 \leq a_i \leq K$ ) 하나가 주어진다. $a_i$ 는 $i$ 번째 티셔츠를 올려야 할 더미 번호이다. 수는 스테판이 티셔츠를 받는 순서대로 주어진다.

출력

스테판이 티셔츠를 올리는 동안 스크립트를 옮겨야 하는 최소 횟수를 자연수 하나로 출력한다. 처음에는 스크립트를 어느 더미에든 둘 수 있으며, 이때의 배치는 옮긴 횟수에 세지 않는다.

힌트

첫 번째 예제에서 스테판은 아무 티셔츠도 오기 전에 스크립트를 1번 더미에 둘 수 있다(이는 옮긴 것으로 세지 않는다). 두 번째 티셔츠가 오기 전에 스크립트를 3번 더미로 옮긴다. 여섯 번째 티셔츠가 오기 전에는 스크립트를 다시 1번 더미로 옮긴다. 이보다 적게 옮기는 것은 불가능하지만, 이것이 스크립트를 옮기는 유일한 방법은 아니다.

예제2

예제 1
입력
```
8 3
3
1
2
1
1
3
3
2
```
예상 출력
```
2
```
예제 2
입력
```
1 2
1
```
예상 출력
```
0
```