인형 정리

문제

어떤 JOI 관계자는 장난감 가게에서 일하고 있다. 오늘은 가게 안에 있는 인형 코너를 정리하게 되었다.

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

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

• N 개의 인형 중 몇 개를 골라 선반에서 꺼낸다. 꺼내지 않은 인형의 위치는 움직이지 않는다.
• 꺼낸 인형을 원하는 순서대로 선반의 비어 있는 구획에 되돌려 놓는다.

재배열한 후에는, 같은 종류의 인형이 모두 연속해서 선반에 놓여 있어야 한다. 재배열하기 위해 꺼내는 인형 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 1 + N 줄로 이루어진다.

1 번째 줄에는 2 개의 정수 N, M (1 ≦ N ≦ 100000, 1 ≦ M ≦ 20) 이 공백으로 구분되어 쓰여 있으며, 인형이 N 개 있고 종류가 M 종류 있음을 나타낸다.

이어지는 N 줄에는 각각 1 이상 M 이하의 정수가 쓰여 있다. N 줄 중 i 번째 줄 (1 ≦ i ≦ N) 에 쓰인 정수는, 선반의 왼쪽에서 i 번째 구획에 놓인 인형의 종류를 나타낸다. 각 종류에 대해, 적어도 1 개의 인형이 존재함이 보장된다.

출력

재배열하기 위해 꺼내는 인형 개수의 최솟값을 한 줄에 출력한다.

예제 입력 1

7 2
1
2
2
2
1
2
1

예제 출력 1

2

예제 1 에서는, 처음에 놓여 있는 인형의 종류가 왼쪽부터 차례로 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

예제 출력 2

7