给定一个包含 $N$ 个整数的数组：$[A_1, A_2, \dots, A_N]$。

子序列可以通过从数组中删除零个或多个元素且不改变剩余元素顺序得到。例如，$[2, 1, 2]$、$[3, 3]$、$[1]$ 和 $[3, 2, 1, 3, 2]$ 是数组 $[3, 2, 1, 3, 2]$ 的子序列，而 $[1, 2, 3]$ 不是数组 $[3, 2, 1, 3, 2]$ 的子序列。

如果一个子序列包含至多两个不同的值，且每个元素与其相邻元素不同，则称该子序列是“可微波的”（microwavable）。例如，$[2, 1, 2]$、$[3, 2, 3, 2]$ 和 $[1]$ 是可微波的，而 $[3, 3]$ 和 $[3, 2, 1, 3, 2]$ 不是可微波的。

定义函数 $f(x, y)$ 为数组 $A$ 中所有元素仅由 $x$ 或 $y$ 组成的最长可微波子序列的长度。求所有 $1 \le x < y \le M$ 的 $f(x, y)$ 之和。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($1 \le N, M \le 300\,000$)。 第二行包含 $N$ 个整数 $A_i$ ($1 \le A_i \le M$)。

输出格式

输出一个整数，表示所有 $1 \le x < y \le M$ 的 $f(x, y)$ 之和。

样例

输入 1

5 4
3 2 1 3 2

输出 1

13

说明 1

$f(1, 2)$ 的值为 3，取自子序列 $[2, 1, 2]$，可以通过删除 $A_1$ 和 $A_4$ 得到。$f(1, 3)$ 的值为 3，取自子序列 $[3, 1, 3]$，可以通过删除 $A_2$ 和 $A_5$ 得到。$f(2, 3)$ 的值为 4，取自子序列 $[3, 2, 3, 2]$，可以通过删除 $A_3$ 得到。$f(1, 4)$、$f(2, 4)$ 和 $f(3, 4)$ 的值均为 1。

输入 2

3 3
1 1 1

输出 2

2

说明 2

$f(1, 2)$ 和 $f(1, 3)$ 的值均为 1，而 $f(2, 3)$ 的值为 0。