문제
어떤 JOI 관계자가 장난감 가게에서 일한다. 오늘은 가게 안 인형 코너를 정리하기로 했다. 인형 코너 선반에는 인형 \(N\)개가 왼쪽에서 오른쪽으로 한 줄로 놓여 있다. 선반은 칸막이로 \(N\)칸으로 나뉘어 있고, 한 칸에 인형 \(1\)개를 둔다. 이 가게는 인형을 모두 \(M\)종류 팔고, 종류에는 \(1\)부터 \(M\)까지 번호가 붙어 있다. 선반의 인형 \(N\)개는 각각 이 \(M\)종류 가운데 하나이다. 또 각 종류는 적어도 \(1\)개 있다. 보기 좋게 하려고, 같은 종류의 인형이 모두 이어져 놓이도록 다시 놓고 싶다. 다음 방법으로 인형을 다시 놓는다.
다시 놓은 뒤에는 같은 종류의 인형이 모두 이어져 있어야 한다. 다시 놓기 위해 꺼내는 인형 개수의 최솟값을 구하라. |
입력
입력은 다음 형식으로 주어진다.
\(N\) \(M\)
\(T_1\)
\(T_2\)
\(\vdots\)
\(T_N\)
- 입력은 \(1+N\)줄이다.
- 첫째 줄에 정수 \(N\), \(M\)이 공백 하나로 구분되어 주어진다. 인형이 \(N\)개, 종류가 \(M\)가지임을 나타낸다.
- 이어지는 \(N\)줄 각각에 \(1\) 이상 \(M\) 이하의 정수가 주어진다. \(i\)번째 줄(\(1 \le i \le N\))의 정수는 선반 왼쪽에서 \(i\)번째 칸에 놓인 인형의 종류이다. 각 종류는 적어도 \(1\)개 있음이 보장된다.
- \(1 \le N \le 100000\)
- \(1 \le M \le 20\)
- 입력되는 값은 모두 정수이다.
출력
다음 형식으로 출력한다.
첫째 줄에, 다시 놓기 위해 꺼내는 인형 개수의 최솟값을 출력한다.
예시 1
입력
7 2
1
2
2
2
1
2
1
출력
2
설명
처음 놓인 인형 종류는 왼쪽부터 \(1, 2, 2, 2, 1, 2, 1\)이다. 왼쪽에서 \(1\)번째와 \(6\)번째 인형을 꺼내, \(1\)번째 칸에 종류 \(2\), \(6\)번째 칸에 종류 \(1\)을 두면 꺼내는 개수가 \(2\)로 최소가 된다.
예시 2
입력
12 4
1
3
2
4
2
1
2
3
1
1
3
4
출력
7