CF1167E.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.

给你一个由 $n$ 个整数 $a_1, a_2, \dots , a_n$ 构成的数组以及一个整数 $x$。保证对每个 $i$，均有 $1 \le a_i \le x$。

定义函数 $f(l, r)$：将数组 $a$ 中所有满足 $l \le a_i \le r$ 的元素全部删除，并返回剩余元素构成的数组。例如，若 $a = [4, 1, 1, 4, 5, 2, 4, 3]$，则 $f(2, 4) = [1, 1, 5]$。

你的任务是计算满足 $1 \le l \le r \le x$ 且 $f(l, r)$ 按非降序排列的数对 $(l, r)$ 的个数。注意：空数组也被视为已排序。

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$).

第一行包含两个整数 $n$ 和 $x$（$1 \le n, x \le 10^6$）—— 分别表示数组 $a$ 的长度及其元素的上限。

第二行包含 $n$ 个整数 $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.

输出满足 $1 \le l \le r \le x$ 且 $f(l, r)$ 按非降序排列的数对 $(l, r)$ 的个数。

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)$.

在第一个测试用例中，正确的数对为 $(1, 1)$、$(1, 2)$、$(1, 3)$ 和 $(2, 3)$。

在第二个测试用例中，正确的数对为 $(1, 3)$、$(1, 4)$、$(2, 3)$、$(2, 4)$、$(3, 3)$ 和 $(3, 4)$。