전자레인지 가능한 부분 수열

길이가 $N$인 정수 배열 $[A_1, A_2, \dots, A_N]$이 주어진다.

배열에서 원소를 순서를 바꾸지 않고 0개 이상 제거해서 얻은 수열을 부분 수열이라고 한다. 예를 들어 $[3, 2, 1, 3, 2]$의 부분 수열에는 $[2, 1, 2]$, $[3, 3]$, $[1]$, $[3, 2, 1, 3, 2]$가 있고, $[1, 2, 3]$은 없다.

부분 수열에 서로 다른 값이 최대 2개만 포함되고, 각 원소가 바로 옆 원소와 값이 다르면 그 부분 수열을 전자레인지 가능하다고 한다. 예를 들어 $[2, 1, 2]$, $[3, 2, 3, 2]$, $[1]$은 전자레인지 가능하고, $[3, 3]$과 $[3, 2, 1, 3, 2]$는 그렇지 않다.

$f(x, y)$는 모든 원소가 $x$ 또는 $y$인 $A$의 전자레인지 가능한 부분 수열 중 가장 긴 것의 길이이다. $1 \le x < y \le M$인 모든 $(x, y)$에 대해 $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)$의 합을 하나의 정수로 출력한다.