시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 151 46 30 33.708%

문제

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

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

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

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

입력

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

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

출력

최소 비용을 출력하라.

예제 입력 1

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

예제 출력 1

11

힌트

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

W3sicHJvYmxlbV9pZCI6IjYxMDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZGRcdWIyZjkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NTggXHVjMmRkXHViMmY5XHVjNzQwIE5cdWI5YzhcdWI5YWNcdWM3NTggXHVjMThjXHViNGU0XHVjNWQwXHVhYzhjIE1cdWFjMWNcdWM3NTggXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzgxY1x1YWNmNVx1ZDU3NCBcdWM4ZmNcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxOGNcdWI0ZTRcdWM3NDAgXHVjNzkwXHVjMmUwXHViNGU0XHVjNzc0IFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWM3NGNcdWMyZGQgUGlcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc0MCBcdWIyZTRcdWM3NGMgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YzE4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWM3NGNcdWMyZGRcdWM3NDQgXHVhY2Y1XHVhZTA5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YjRlNFx1YzViNFx1YzYyNFx1YjI5NCBcdWMxOGNcdWI0ZTRcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YWRmOFx1YjhmOVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDhcdWIyZTQuIFsxIH4gNF0gXC8gWzUgfiA3XSBcLyBbOCB+IDEwXSBcdWM3NzRcdWI3ZjAgXHVjMmRkXHVjNzNjXHViODVjLjxcL2xpPlxyXG5cdDxsaT5cdWFkZjhcdWI4ZjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzE4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWM3NGNcdWMyZGRcdWM3NDQgXHVjODFjXHVhY2Y1XHVkNTU4XHViMjk0IFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwIChcdWQ1NzRcdWIyZjkgXHVhZGY4XHViOGY5XHVjNWQwXHVjMTFjIFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWM3NGNcdWMyZGRcdWM3NTggXHVkNTY5XHVjOWQxXHVkNTY5IFx1ZDA2Y1x1YWUzMCleMiBcdWM3NzRcdWIyZTQuIFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWMyMThcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTU4XHViYTc0LCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzIxOFx1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjODFjXHVhY2YxXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3M2NcdWI4NWMgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzgxY1x1YWNmNVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVkNTc0XHVjNTdjIFx1ZDU2MFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIE4sIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbHQ7PSBNICZsdDs9IE4gJmx0Oz0gNDAwMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBQaVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsdDs9IFBpICZsdDs9IE0pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPlsxXSBbMl0gWzNdIFs0XSBbNSwgNl0gWzcsIDgsIDksIDEwLCAxMV0gWzEyXSBbMTNdIFx1YWNmYyBcdWFjMTlcdWM3NzQgXHViYjM2XHVjNzNjXHViYTc0LCAxICsgMSArIDEgKyAxICsgMSArIDQgKyAxICsgMSA9IDExXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZTBcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2MTAxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2xlYW5pbmcgVXAiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBnb29kIG9sZCBkYXlzLCBGYXJtZXIgSm9obiBzZXJ2ZWQgYSBib3JpbmcgY3Vpc2luZSBjb21wcmlzaW5nIGJ1dCBhIHNpbmdsZSB0eXBlIG9mIGNvdyBmb29kIHRvIGhpcyBOICgxICZsdDs9IE4gJmx0Oz0gNDAwMDApIHByaXplIGRhaXJ5IGNvd3MuIFRpbWVzIGNoYW5nZS4gVG9kYXkgaGUgc2VydmVzIHRoZSBoZXJkIGEgdG90YWwgb2YgTSAoMSAmbHQ7PSBNICZsdDs9IE4pIGRpZmZlcmVudCB0eXBlcyBvZiBmb29kIChjb252ZW5pZW50bHkgbnVtYmVyZWQgMS4uTSkuPFwvcD5cclxuXHJcbjxwPlRoZSBjb3dzIGFyZSBwaWNreS4gQ293IGkgaGFzIGEgc2luZ2xlIGZvb2QgcHJlZmVyZW5jZSBQX2kgKDEgJmx0Oz0gUF9pICZsdDs9IE0pIGFuZCB3aWxsIGVhdCBvbmx5IHRoYXQgZmF2b3JpdGUgZm9vZC48XC9wPlxyXG5cclxuPHA+RWFjaCBkYXkgYXQgZmVlZGluZyB0aW1lIEZKIGNvbnZlcnRzIHRoZSBiYXJuIGludG8gYSB0YXN0ZWZ1bGx5IGxpdCBjYWZldGVyaWEuIFRoZSBjb3dzIGxpbmUgdXAgb3V0c2lkZSB0byBlbnRlciB0aGUgY2FmZXRlcmlhIGluIG9yZGVyIG9mIHRoZWlyIHByZXZpb3VzbHktbWVudGlvbmVkIGNvbnZlbmllbnQgaW5kZXggbnVtYmVyLjxcL3A+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCB3aXRoIHNvIG1hbnkgdHlwZXMgb2YgZm9vZCwgY2xlYW5pbmcgdXAgYWZ0ZXJ3YXJkcyBpcyB2ZXJ5IHRpbWUtY29uc3VtaW5nLiBJZiBGYXJtZXIgSm9obiBpcyBzZXJ2aW5nIEsgZGlmZmVyZW50IHR5cGVzIG9mIGZvb2QsIGl0IHRha2VzIGhpbSBLKksgdW5pdHMgb2YgdGltZSB0byBjbGVhbiB0aGUgYmFybi48XC9wPlxyXG5cclxuPHA+VG8gc2F2ZSB0aW1lLCBGSiBzZXJ2ZXMgdGhlIGNvd3MgaW4gY29udGlndW91cyBncm91cHMgZnJvbSB0aGUgbGluZS4gQWZ0ZXIgZWFjaCBncm91cCwgaGUgY2xlYW5zIHVwIHRoZSBiYXJuIGFuZCBzZXRzIG91dCB0aGUgZm9vZCBmb3IgdGhlIG5leHQgZ3JvdXAgKG9mIGNvdXJzZSwgaGUgb25seSBzZXRzIG91dCBmb29kIHRoYXQgY293cyBpbiB0aGUgYW55IGdpdmVuIGdyb3VwIHdpbGwgZWF0KS4gRGV0ZXJtaW5lIHRoZSBtaW5pbXVtIGFtb3VudCBvZiB0b3RhbCB0aW1lIEZKIG11c3Qgc3BlbmQgY2xlYW5pbmcgdGhlIGJhcm4uIEVhY2ggZ3JvdXAgY29uc2lzdHMgb2YgdGhlIG5leHQgY29udGlndW91cyBncm91cCBvZiBjb3dzIGZyb20gdGhlIGxpbmU7IGVhY2ggY293IGJlbG9uZ3MgdG8gZXhhY3RseSBvbmUgZ3JvdXA7IGFuZCB0aGUgYmFybiBtdXN0IGJlIGNsZWFuZWQgdXAgYWZ0ZXIgZXZlcnkgZ3JvdXAsIGluY2x1ZGluZyB0aGUgbGFzdCBvbmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgTTxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IExpbmUgaSsxIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXI6IFBfaTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyOiB0aGUgbWluaW11bSBhbW91bnQgb2YgdGltZSBGSiBtdXN0IHNwZW5kIGNsZWFuaW5nIHRoZSAmbmJzcDtiYXJuLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgZmlyc3QgZm91ciBncm91cHMgY29udGFpbiBvbmUgY293IGVhY2guIFRoZSBmaWZ0aCBncm91cCBjb250YWlucyB0d28gY293cyB3aG8gcHJlZmVyIGZvb2QgIzIgKHJlcXVpcmluZyBvbmUgdW5pdCBvZiB0aW1lKS4gVGhlIHNpeHRoIGdyb3VwIGNvbnRhaW5zIGNvd3MgcHJlZmVycmluZyBmb29kcyAzLCA0LCAzLCA0LCAzIChhbmQgcmVxdWlyZXMgZm91ciB1bml0cyBvZiB0aW1lIHRvIGNsZWFuKS4gVGhlIGxhc3QgdHdvIGdyb3VwcyBjb250YWluIG9uZSBjb3cgZWFjaC4gVGhlIHRvdGFsIHRpbWUgaXMgMTEuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d