시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 135 39 24 31.169%

문제

농부 존의 식당은 N마리의 소들에게 M개의 음식을 제공해 주고 있다.

소들은 자신들이 선호하는 음식 Pi를 가지고 있는데, 농부 존은 다음 방법으로 소들에게 음식을 공급한다.

  • 들어오는 소들을 순서대로 그룹으로 나눈다. [1 ~ 4] / [5 ~ 7] / [8 ~ 10] 이런 식으로.
  • 그룹에 있는 소들에게 음식을 제공하는 데 드는 비용은 (해당 그룹에서 선호하는 음식의 합집합 크기)^2 이다. 음식을 수로 생각하면, 서로 다른 수들의 개수의 제곱이다.

최소 비용으로 음식을 제공하려면 어떻게 해야 할까?

입력

첫번째 줄에 N, M이 주어진다. (1 <= M <= N <= 40000)

이후 N개의 줄에 Pi가 주어진다. (1 <= Pi <= M)

출력

최소 비용을 출력하라.

예제 입력

13 4
1
2
1
3
2
2
3
4
3
4
3
1
4

예제 출력

11

힌트

[1] [2] [3] [4] [5, 6] [7, 8, 9, 10, 11] [12] [13] 과 같이 묶으면, 1 + 1 + 1 + 1 + 1 + 4 + 1 + 1 = 11의 비용이 든다.