题目背景

小萝卜喜欢帽子哥哥。有多喜欢呢？每次和他出去玩都要计划好久的！

萝卜呢，有很多件好看的衣服。因此计划的一部分就是：每次出去玩都和上次穿的不一样。

可是原先的计划表非常不合理，因此小萝卜需要花很多时间来修改。因为出去玩的时间非常宝贵，所以她认为修改次数要尽量小。

题目描述

萝卜有 $m$ 件衣服，计划表为长为 $n$ 的序列 $a$，则 $a_i$ 为 $[1,m]$ 中的整数，表示当天穿的是哪一件衣服。萝卜保证他的衣服至少有两件。

萝卜每次修改可以将 $a_i$ 修改为 $[1,m]$ 中任何一个整数。对于一个序列 $a$，他的困难程度定义为：使得 $a_1,a_2,\cdots,a_n$ 中任意相邻两个数都不同的最小操作次数。设这个值为 $f(a,m)$。

对于序列 $a$，萝卜想请你求出其所有子段的困难程度之和，即：

$$\sum_{1\le l\le r\le n}f([a_l,a_{l+1},\cdots,a_r],m) $$

输入格式

第一行两个正整数 $n,m$，表示计划表长度与衣服的件数。

接下来一行 $n$ 个正整数 $a_i$，表示计划表。

输出格式

一行一个整数，表示答案。

10 2
1 1 2 2 2 1 1 2 2 1

81

3 3
2 2 3

2

30 30
26 4 4 4 20 28 13 13 2 2 2 2 2 24 24 24 24 24 24 24 29 29 29 29 29 2 2 2 2 2

1905

提示

【样例解释】

对于样例 $1$ 的整个原序列，一种最优的修改方案是将其修改为 $[2,1,2,1,2,1,2,1,2,1]$，修改次数是 $4$，故困难程度为 $4$。

对于样例 $2$，所有子段及其困难程度如下：

• $[2]$，困难程度为 $0$。
• $[2,2]$，困难程度为 $1$。
• $[2,2,3]$，困难程度为 $1$。
• $[2]$，困难程度为 $0$。
• $[2,3]$，困难程度为 $0$。
• $[3]$，困难程度为 $0$。

故总和为 $2$。

对于样例 $3$，暂时不能给你一个明确的答复。

【数据范围】

本题开启捆绑测试。

子任务	分数	$n\le$	$m\le$	特殊性质
$1$	$10$
$2$	$20$	$10^3$	$10^9$
$3$	$30$	$2\times10^5$		$m>2$
$4$	$40$

对于 $100\%$ 的数据，$1\le n\le 2\times10^5$，$2\le m\le 10^9$。