说明

给定一个包含 $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]$ 的子序列。

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

定义函数 $f(x, y)$ 为数组 $A$ 中最长的 可微波 子序列的长度，且该子序列中的每个元素要么是 $x$，要么是 $y$。请计算所有满足 $1 \leq x < y \leq M$ 的 $f(x, y)$ 之和。

输入格式

第一行包含两个整数 $N$ $M$（$1 \leq N, M \leq 300\,000$）。

第二行包含 $N$ 个整数 $A_i$（$1 \leq A_i \leq M$）。

输出格式

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

5 4
3 2 1 3 2

13

3 3
1 1 1

2

提示

样例输入/输出 #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 的解释

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

翻译由 DeepSeek V3.2 完成