메뉴 건너뛰기

문제

00b49 가난한 화가 0  

시간메모리제출 올바른 답 비율
1초200MB
17
6
35.3%


나의 횟수나의 최근 판정시도 성공 비율
76
85.7%
가난한 화가 

가난한 천재 화가인 주영이는 그림을 그리기에는 다소 좁고 낡은 책상을 쓰고 있다. 주변에서도 이 책상을 바꾸라고 제안하지만 자신의 어릴 적 추억이 담겨있는 책상이라 바꿀 생각이 전혀 없다.

문제는 책상이 좁아서 물감 전체를 책상 위에 올려놓고 쓸 수 없다. 결국 바닥에 물감을 내려놓고 필요한 색만을 골라서 책상에 올려놓는다.

책상 위에 사용하고자 하는 색이 없으면,
 1) 책상 위에 물감 중 하나를 바닥에 내려놓고 
 2) 필요한 색을 골라 책상 위에 올려놓기를 반복한다. 

매번 이런 과정이 불편한 주영이는 고민 끝에 그날 하루 사용할 물감의 색과 사용순서를 정해서 물감을 바닥에 내려놓는 횟수를 최소로 하고 싶었다.

사용순서
1 빨강
2 파랑
3 노랑
4 보라
5 빨강


예를 들어 좁은 책상에 물감을 2개 정도 올려놓고 쓸 수 있을 때, 물감의 사용 순서가 아래와 같이 주어진다면, 빨강, 파랑물감을 순서대로 책상에 올려놓은 다음, 파랑물감을 바닥에 내려놓고 노랑물감을 선택한다, 그리고 사용 후, 다시 노랑물감을 내려놓고 보라색 물감을 올려놓으면 2번만 물감을 바닥에 내려놓으면 된다. 

입력

첫 줄에는 책상 위에 올려놓을 수 있는 물감의 수 N (1 ≤ N ≤ 100)과 물감의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다.

두 번째 줄에는 사용할 물감색의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있으며, 물감의 색은 연속적으로 중복될 수 있다.

출력

물감을 바닥에 내려놓는 최소횟수를 출력한다.

예시
1입력
2 5
1 2 3 4 1
출력
2
출처
2017. 정보올림피아드 고등부 2번
위로