Sum of Difficulties of Contiguous Subarrays

Carrot has m pieces of clothing (with m ≥ 2) and a schedule for n days represented by a sequence a of length n. For each day i, the value a_i (an integer in the range [1, m]) indicates which piece of clothing is worn.

You are allowed to modify the schedule. In each modification you may change a single element a_i to any integer in [1, m]. The difficulty of a sequence a is defined as the minimum number of modifications required to ensure that every pair of adjacent days feature different clothes. In other words, after modifications, for every valid index i we must have:

$$a_i \neq a_{i+1}.$$

For a given sequence a, let the difficulty be denoted by $$f(a,m).$$ Carrot wants you to compute the sum of difficulties for all contiguous subarrays of a. Formally, you need to calculate:

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

Note: It is guaranteed that m ≥ 2.

inputFormat

The first line contains two integers n and m.

The second line contains n integers a₁, a₂, \dots, a_n (each between 1 and m) representing the schedule.

outputFormat

Output a single integer — the sum of difficulties for all contiguous subarrays of a.

sample

3 2
1 1 1

4

</p>