CF2045I.Microwavable Subsequence

给定一个整数数组 $[A_1, A_2, \dots, A_N]$，数组长度为 $N$。

从数组中移除零个或多个元素，并保持剩余元素的顺序不变，就可以得到一个子序列。例如，$[2, 1, 2]$、$[3, 3]$、$[1]$ 和 $[3, 2, 1, 3, 2]$ 都是数组 $[3, 2, 1, 3, 2]$ 的子序列，而 $[1, 2, 3]$ 不是。

如果某个子序列最多只包含两种不同的数，并且相邻元素不相同，则称为“微波炉”子序列。例如，$[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$，可以从序列中去掉 $A_1$ 和 $A_4$，得到子序列 $[2, 1, 2]$。$f(1, 3)$ 的值为 $3$，通过去除 $A_2$ 和 $A_5$，得到子序列 $[3, 1, 3]$。$f(2, 3)$ 的值为 $4$，从序列中去除 $A_3$，得到子序列 $[3, 2, 3, 2]$。而 $f(1, 4)$、$f(2, 4)$ 和 $f(3, 4)$ 的值均为 $1$。

样例解释 2

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

本翻译由 AI 自动生成