CF1167E Range Deleting

给定一个包含 $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]$。 你的任务是计算有多少对 $(l, r)$ 满足 $1 \le l \le r \le x$，并且 $f(l, r)$ 得到的数组是非降序排列的。注意，空数组也被认为是有序的。

第一行包含两个整数 $n$ 和 $x$（$1 \le n, x \le 10^6$），分别表示数组 $a$ 的长度和数组元素的上界。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le x$）。

输出满足条件的 $(l, r)$ 对数，其中 $1 \le l \le r \le x$ 并且 $f(l, r)$ 是非降序排列的。

在第一个测试用例中，满足条件的对为 $(1, 1)$、$(1, 2)$、$(1, 3)$ 和 $(2, 3)$。 在第二个测试用例中，满足条件的对为 $(1, 3)$、$(1, 4)$、$(2, 3)$、$(2, 4)$、$(3, 3)$ 和 $(3, 4)$。 由 ChatGPT 4.1 翻译