题目描述

小花狮有一个排成一排、长度为 $n$ 的积木序列，每块积木都有各自的颜色 $c$，我们用一个 $[1, k]$ 之间的正整数来表示，于是这些积木的颜色构成了一个序列 $c_1, c_2, \dots, c_n$。

小花狮能执行若干次操作，每次操作能从序列的头部拿走一段连续的积木，记 $x$ 为这段积木中颜色的种数，那么这次操作的得分为 $x^3$。当所有积木都被拿走后，最终得分便为每次操作的得分之和。请问小花狮在消掉整段序列后，最终得分最大是多少呢？

输入格式