← 返回题目列表

Codeforces · 1167/E

E. 范围删除

中文机器翻译题面 查看原题

给定一个由 $$$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$$$)。

输出

打印 $$$1 \le l \le r \le x$$$ 的对数,使得 $$$f(l, r)$$$ 按非降序排序。

示例

输入 #1

3 3
2 3 1

输出 #1

4

输入 #2

7 4
1 3 1 2 2 4 3

输出 #2

6

注意

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

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