Range Deleting

题意翻译

给定长度为$n$的数组$a$,其中任意$a_i \leq x$ 定义$f(l,r)$为删除$a$中值域在$[l,r]$的数后剩余的数组. 统计满足$1\leq l \leq r \leq x$且$f(l,r)$是非严格不下降序列的数对$(l,r)$的数量。

题目描述

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.

输入输出样例

输入样例 #1

3 3
2 3 1

输出样例 #1

4

输入样例 #2

7 4
1 3 1 2 2 4 3

输出样例 #2

6

说明

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