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