인형 정리

시간 제한2초메모리 제한512 MB

요약

M가지 종류의 인형 N개가 일렬로 놓여 있을 때, 뽑아낸 인형을 다시 끼워 넣어 같은 종류가 모두 연속하도록 만드는 최소로 뽑아야 하는 인형 수를 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 비트 연산, 누적 합
정답자: 아직 제출이 없습니다

문제

JOI 관계자 한 명이 장난감 가게에서 일한다. 오늘은 가게 안의 인형 코너를 정리하게 되었다.

인형 코너의 선반에는 인형 $N$ 개가 왼쪽에서 오른쪽으로 한 줄로 놓여 있다. 선반은 칸막이로 $N$ 개의 칸으로 나뉘어 있고, 한 칸에는 인형을 하나 둔다. 이 가게는 모두 $M$ 종류의 인형을 팔고, 각 종류에는 $1$ 부터 $M$ 까지 번호가 붙어 있다. 선반에 놓인 인형 $N$ 개는 각각 이 $M$ 종류 중 하나이다. 또한 모든 종류의 인형이 적어도 하나씩 있다.

보기 좋게 만들려고 같은 종류의 인형이 모두 선반에 연속해서 놓이도록 인형을 다시 배치하려고 한다. 다음 방법으로 다시 배치하기로 했다.

인형 $N$ 개 중 몇 개를 골라 선반에서 꺼낸다. 꺼내지 않은 인형의 위치는 움직이지 않는다.
꺼낸 인형을 원하는 순서대로 선반의 빈 칸에 다시 놓는다.

다시 배치한 뒤에는 같은 종류의 인형이 모두 선반에 연속해서 놓여 있어야 한다. 다시 배치하려고 꺼내는 인형 개수의 최솟값을 구하는 프로그램을 작성하라.

입력

첫째 줄에 두 정수 $N$ , $M$ ( $1 \le N \le 100\,000$ , $1 \le M \le 20$ )이 공백으로 구분되어 주어진다. 인형이 $N$ 개, 종류가 $M$ 가지라는 뜻이다.

다음 $N$ 개 줄에는 각각 $1$ 이상 $M$ 이하의 정수가 하나씩 주어진다. 이 중 $i$ 번째 줄( $1 \le i \le N$ )의 정수는 선반의 왼쪽에서 $i$ 번째 칸에 놓인 인형의 종류이다. 모든 종류에 대해 그 종류의 인형이 적어도 하나 있음이 보장된다.

출력

다시 배치하려고 꺼내는 인형 개수의 최솟값을 한 줄에 출력한다.

힌트

예제 1에서 처음에 놓인 인형의 종류는 왼쪽부터 차례로 1, 2, 2, 2, 1, 2, 1이다. 꺼내는 인형의 개수를 최소로 하려면 왼쪽에서 1번째와 6번째 인형을 꺼낸 뒤, 왼쪽에서 1번째 칸에 종류 2인 인형을, 6번째 칸에 종류 1인 인형을 놓으면 된다. 이때 꺼내는 인형은 2개이다.

예제2

예제 1
입력
```
7 2
1
2
2
2
1
2
1
```
예상 출력
```
2
```
예제 2
입력
```
12 4
1
3
2
4
2
1
2
3
1
1
3
4
```
예상 출력
```
7
```