음식 진열 배치

면접 대비

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

요약

음식 종류 ID가 한 줄로 늘어서 있을 때, 종류별로 한 덩어리가 되도록 양 끝으로 옮겨야 하는 종류의 최소 개수를 구합니다.

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

문제

친구 토머스는 음식 진열 배치(FDA)를 맞추는 일을 하고 있다. 모든 음식이 긴 줄(테이블)에 한 줄로 놓여 있다. 같은 종류의 음식이 모두 서로 붙어 있으면 FDA가 보기 좋다. 토머스는 한 종류의 음식을 모두 집어서 테이블의 맨 앞이나 맨 뒤에 놓는 방식으로 배치를 바꿀 수 있다. 테이블 양 끝은 옮겨진 음식이 얼마든지 들어갈 만큼 늘어날 수 있다. FDA를 보기 좋게 만드는 데 필요한 최소 재배치 횟수를 구하라. 횟수만 알면 되고 구체적인 방법은 출력하지 않는다.

입력

첫째 줄에 음식의 개수 $n$ ( $1 \le n \le 100000$ )이 주어진다. 둘째 줄에는 $i$ 번째 음식의 종류 번호 $a_i$ ( $1 \le a_i \le 1000000000$ )가 공백으로 구분되어 주어진다.

출력

같은 종류의 음식을 통째로 맨 앞이나 맨 뒤로 옮겨 모든 종류를 한데 모으는 데 필요한 최소 횟수를 출력한다.

힌트

첫 번째 예시에서는 종류 2의 음식을 한쪽 끝으로, 종류 7의 음식을 한쪽 끝으로 옮기면 총 2번이다.

예제2

예제 1
입력
```
15
8 8 2 8 7 8 1 1 3 7 3 4 2 4 7
```
예상 출력
```
2
```
예제 2
입력
```
10
1 2 3 4 5 1 2 3 4 5
```
예상 출력
```
4
```