P15676 [ICPC 2024 Jakarta R] Microwavable Subsequence

给定一个包含 $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)$ 之和。

**样例输入/输出 #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 完成