E. Range Deletingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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).OutputPrint the number of pairs 1 \le l \le r \le x such that f(l, r) is sorted in non-descending order.ExamplesInput
3 3
2 3 1
Output
4
Input
7 4
1 3 1 2 2 4 3
Output
6
NoteIn 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).
3 3
2 3 1

4 
['binary search', 'combinatorics', 'data structures', 'two pointers', '*2100']