희서는 장난감 마트에서 알바를 하고 있다.

오늘은 인형 코너를 정리하게 되었다.

인형 코너의 선반에는 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 개이다.

인형정리 timer 2s memory 256MB

인형정리 2s 256MB