你受雇去粉刷一道栅栏。栅栏由 $n$ 个部分组成，编号为 $1$ 到 $n$。栅栏最终需要使用 $m$ 种颜色进行粉刷，颜色编号为 $1$ 到 $m$。对于每个部分 $i$，其目标颜色 $c_i$ 是已知的。

你的订单还规定了粉刷过程的具体方式。粉刷过程必须恰好分为 $m$ 个阶段。在每个阶段，你可以选择一种颜色 $c \in \{1, \dots, m\}$ 和两个索引 $a, b$（满足 $1 \le a \le b \le n$），并将区间 $a, a+1, \dots, b$ 涂上颜色 $c$。执行这样一个阶段需要 $b - a + 1$ 小时。如果其中某些部分之前已经被涂过颜色，则之前的颜色会被 $c$ 覆盖。初始时，所有部分均未涂色。

题目保证按照上述过程可以将栅栏粉刷成目标状态。然而，你可以自由决定每个阶段的具体操作。由于你是按小时计费的，你希望粉刷过程耗时尽可能长。

考虑以下示例。设 $n = 4, m = 3$，目标颜色序列为 $(2, 1, 2, 3)$。我们可以这样粉刷栅栏（此处 $0$ 表示未涂色）： $(0, 0, 0, 0) \to (0, 0, 0, 3) \to (2, 2, 2, 3) \to (2, 1, 2, 3)$。 这样的粉刷过程耗时 $1 + 3 + 1 = 5$ 小时。然而，如果我们按照以下方式进行，可以耗时 $8$ 小时（从而赚取更多报酬）： $(0, 0, 0, 0) \to (3, 3, 3, 3) \to (2, 2, 2, 3) \to (2, 1, 2, 3)$。

计算可能的最大粉刷时间。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 10^5, 1 \le m \le 5000$)，分别表示栅栏的部分数量和使用的颜色数量。第二行包含 $n$ 个整数 $c_1, \dots, c_n$ ($1 \le c_i \le m$)，描述了各个部分的目标颜色。保证 $m$ 种颜色中的每一种在序列中至少出现一次，即 $\{c_1, \dots, c_n\} = \{1, \dots, m\}$。

输出格式

输出按照所述规则进行粉刷时，可能的最大粉刷时间。

样例

输入 1

4 3
2 1 2 3

输出 1

8