A12615. Range Deleting

You are given an array consisting of $n$ integers $a_1, a_2, \dots , a_n$ and an integer $x$ . It is guaranteed that for every $i$ , $1 \le a_i \le x$ .

Let's denote a function $f(l, r)$ which erases all values such that $l \le a_i \le r$ from the array $a$ and returns the resulting array. For example, if $a = [4, 1, 1, 4, 5, 2, 4, 3]$ , then $f(2, 4) = [1, 1, 5]$ .

Your task is to calculate the number of pairs $(l, r)$ such that $1 \le l \le r \le x$ and $f(l, r)$ is sorted in non-descending order. Note that the empty array is also considered sorted.

The first line contains two integers $n$ and $x$ ( $1 \le n, x \le 10^6$ ) — the length of array $a$ and the upper limit for its elements, respectively.

The second line contains $n$ integers $a_1, a_2, \dots a_n$ ( $1 \le a_i \le x$ ).

Print the number of pairs $1 \le l \le r \le x$ such that $f(l, r)$ is sorted in non-descending order.

In the first test case correct pairs are $(1, 1)$ , $(1, 2)$ , $(1, 3)$ and $(2, 3)$ .

In the second test case correct pairs are $(1, 3)$ , $(1, 4)$ , $(2, 3)$ , $(2, 4)$ , $(3, 3)$ and $(3, 4)$ .