웨딩 DJ

늘 DJ가 되고 싶었는데, 드디어 첫 기회가 왔습니다! 결혼식에서 리스트에 적힌 순서대로 틀 곡 목록이 있습니다. 각 곡에는 "fun level"이 있습니다. 문제는 B\&G(신부와 신랑)가 fun level이 낮은 곡 뒤에 다른 곡이 나오는 것을 원하지 않는다는 점입니다. 즉, B\&G는 곡들의 fun level이 한 번도 줄어들지 않을 때만 그 플레이리스트를 좋다고 봅니다. 다행히 곡의 fun level은 조정할 수 있습니다. fun level이 $x$인 곡을 모두 fun level $y$로 바꿀 수 있습니다. 예를 들어 fun level 10인 곡을 모두 fun level 7로(또는 fun level 18로) 바꿀 수 있습니다. 다음을 참고하세요.

• fun level $x$인 곡을 모두 fun level $y$로 바꾸면, 그 곡들이 모두 바뀌더라도 한 번의 변경으로 셉니다.
• fun level $x$인 곡을 바꾸면 fun level $x$인 곡이 모두 바뀌며, 그중 일부만 골라 바꿀 수는 없습니다.
• fun level $x$인 곡을 모두 fun level $y$로 바꾼 뒤, fun level $y$인 곡을 모두 fun level $z$로 바꾸기로 했다면, 두 번째 변경은 원래 목록이 아니라 갱신된 목록에 적용됩니다. 예를 들어 원래 목록이 {… 3 … 8 … 3 … 8 … 3 …}이고, fun level 3을 8로 바꾼 다음 fun level 8을 2로 바꾸기로 했다면, 두 곡이 아니라 다섯 곡의 fun level이 2로 바뀝니다.

곡들의 fun level 순서가 주어질 때, 플레이리스트의 곡 fun level이 줄어들지 않도록 레벨 $x$인 곡을 모두 레벨 $y$로 바꾸는 방식으로 필요한 플레이리스트 조정의 최소 횟수를 구하세요.

첫 줄에 플레이리스트의 곡 수를 나타내는 정수 $n$ ($1 \le n \le 100{,}000$)이 주어집니다. 다음 줄에는 곡이 리스트에 나타나는 순서대로 각 곡의 fun level을 나타내는 공백으로 구분된 정수 $n$개가 주어집니다. 각 fun level은 1 이상 1,000,000,000 이하입니다.

플레이리스트의 fun level이 줄어들지 않도록 만드는 조정 횟수의 최솟값을 출력하세요.

첫 번째 입출력 예시에 대한 설명:

리스트를 줄어들지 않게 만드는 한 가지 방법은 다음과 같습니다.

• fun level 7인 곡을 모두 1로 바꿉니다.
• fun level 8인 곡을 모두 3으로 바꿉니다.
• fun level 5인 곡을 모두 3으로 바꿉니다.

총 3번 변경합니다.