문제
희서는 장난감 마트에서 알바를 하고 있다.
오늘은 인형 코너를 정리하게 되었다.
인형 코너의 선반에는 N개의 인형을 왼쪽에서 오른쪽으로 일렬로 늘어놓을 수 있다.
선반은 N개의 구획으로 구분되어 있으며, 하나의 구획에 1 개의 인형을 놓는다.
이 장난감 마트는 총 M종류의 인형을 팔고 있으며, 각각 1부터 M까지 번호가 매겨져있다.
선반에 정렬된 N개의 인형은 각각 M종류 중 하나이다. 또한 각 종류의 인형은 적어도 1개는 존재한다.
희서는 모양을 좋게 하기 위하여 같은 종류의 인형이 모두 연속으로 되도록 다음과 같은 방법으로 인형을 정렬하고자 한다.
* N개의 인형 중 일부를 선택하여 선반에서 꺼낸다.
* 꺼낸 인형을 좋아하는 순서대로 선반 빈 구획에 다시 집어넣는다.
입력 예 1을 보자.
먼저 놓여있는 인형의 종류는 2종류이고 왼쪽에서 오른쪽으로 1, 2, 2, 2, 1, 2, 1로 7개의 인형이 진열되어 있다.
같은 종류끼리 정렬하는데 꺼낸 인형의 개수를 최소화하려면
왼쪽에서 1 번째와 6 번째 인형을 꺼내 왼쪽에서 1 번째로 유형 2의 인형을 왼쪽에서 6 번째로 유형 1의 인형을 배치한다.
이 때 꺼낸 인형의 개수는 2 개이다.
입력
입력은 1 + N 행된다.
첫 번째 줄에는 두 개의 정수 N, M (1 ≦ N ≦ 100000 1 ≦ M ≦ 20)가 공백을 구분으로 작성되었으며,
인형이 N 개의 있고, 종류가 M 종류 있다는 것을 나타낸다.
다음 N개의 행에는 각각 1 이상 M 이하의 정수가 적혀있다.
N 행 중 i 번째 줄 (1 ≦ i ≦ N)에 쓰인 정수는 선반의 왼쪽에서 i 번째 구획에 놓인 인형의 종류를 나타낸다.
각 유형에 대해 적어도 1 개의 인형이 존재하는 것이 보장된다.
출력
정렬을 위하여 꺼낸 인형 개수의 최소값을 하나의 행에 출력한다.
예제1
입력
72
1
2
2
2
1
2
1
출력
2
예제2
입력
124
1
3
2
4
2
1
2
3
1
1
3
4
출력
7
출처
JOI 2017 예선