Microwavable Subsequence

Time limit1sMemory limit2048 MB

Summary

Given an array, find the longest subsequence using only x and y with no equal adjacent elements, and sum these lengths over all pairs x < y up to M.

Level: Medium7 of 10
Topics: Array, Segment tree, Hash map
Solved: No attempts yet

Problem

You are given an array of $N$ integers $[A_1, A_2, \dots, A_N]$ .

A subsequence is obtained from an array by removing zero or more elements without changing the order of the remaining elements. For example, $[2, 1, 2]$ , $[3, 3]$ , $[1]$ , and $[3, 2, 1, 3, 2]$ are subsequences of $[3, 2, 1, 3, 2]$ , but $[1, 2, 3]$ is not.

A subsequence is microwavable if it contains at most two distinct values and each element differs from its adjacent elements. For example, $[2, 1, 2]$ , $[3, 2, 3, 2]$ , and $[1]$ are microwavable, while $[3, 3]$ and $[3, 2, 1, 3, 2]$ are not.

Let $f(x, y)$ be the length of the longest microwavable subsequence of $A$ in which every element is either $x$ or $y$ . Find the sum of $f(x, y)$ over all $1 \le x < y \le M$ .

Input

The first line contains two integers $N$ and $M$ ( $1 \le N, M \le 300\,000$ ).

The second line contains $N$ integers $A_i$ ( $1 \le A_i \le M$ ).

Output

Print a single integer: the sum of $f(x, y)$ over all $1 \le x < y \le M$ .

Examples2

Example 1
Input
```
5 4
3 2 1 3 2
```
Expected output
```
13
```
Example 2
Input
```
3 3
1 1 1
```
Expected output
```
2
```