식당

시간 제한1초메모리 제한128 MB

요약

N마리의 소가 좋아하는 음식이 순서대로 주어질 때, 연속한 구간으로 나누어 각 구간의 서로 다른 음식 가짓수의 제곱의 합을 최소로 만든다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 분할 정복, 투 포인터, 누적 합
정답자: 아직 제출이 없습니다

문제

농부 존의 식당은 소 $N$ 마리에게 $M$ 종류의 음식을 제공한다.

각 소 $i$ 는 자신이 선호하는 음식 $P_i$ 를 하나 가지고 있으며, 농부 존은 다음 규칙으로 음식을 나누어 준다.

식당에 들어오는 소들을 들어온 순서대로 연속한 그룹으로 나눈다. 예를 들어 $[1 \sim 4] / [5 \sim 7] / [8 \sim 10]$ 처럼 맨 앞에서부터 끊어서 묶는다.
한 그룹에 음식을 제공하는 비용은 (그 그룹에 속한 소들이 선호하는 음식의 서로 다른 종류의 수) $^2$ 이다. 즉 음식을 수로 보면, 그룹 안에 등장하는 서로 다른 수의 개수를 제곱한 값이다.

모든 소에게 음식을 제공하는 데 드는 전체 비용의 최솟값을 구하여라.

입력

첫째 줄에 두 정수 $N$ 과 $M$ 이 공백으로 구분되어 주어진다. ( $1 \le M \le N \le 40000$ )

이어지는 $N$ 개의 줄에 각 소가 선호하는 음식 $P_i$ 가 소가 들어온 순서대로 한 줄에 하나씩 주어진다. ( $1 \le P_i \le M$ )

출력

모든 소에게 음식을 제공하는 최소 비용을 한 줄에 출력한다.

힌트

예를 들어 예제 입력에서 소들을 (들어온 순서대로) $[1]\,[2]\,[3]\,[4]\,[5, 6]\,[7, 8, 9, 10, 11]\,[12]\,[13]$ 과 같이 묶으면, 각 그룹의 비용을 더하여 $1 + 1 + 1 + 1 + 1 + 4 + 1 + 1 = 11$ 이 된다.

예제4

예제 1
입력
```
13 4
1
2
1
3
2
2
3
4
3
4
3
1
4
```
예상 출력
```
11
```
예제 2
입력
```
1 1
1
```
예상 출력
```
1
```
예제 3
입력
```
4 4
1
2
3
4
```
예상 출력
```
4
```
예제 4
입력
```
5 2
1
2
1
2
1
```
예상 출력
```
4
```