Range Deleting

You are given an array consisting of n integers a_1, a_2, ... , a_n and an integer x. It is guaranteed that for every i, 1 ≤ a_i ≤ x.

Let's denote a function f(l, r) which erases all values such that l ≤ a_i ≤ 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 ≤ l ≤ r ≤ x and f(l, r) is sorted in non-descending order. Note that the empty array is also considered sorted.

Input

The first line contains two integers n and x (1 ≤ n, x ≤ 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, ... a_n (1 ≤ a_i ≤ x).

Output

Print the number of pairs 1 ≤ l ≤ r ≤ x such that f(l, r) is sorted in non-descending order.

Examples

Input

3 3 2 3 1

Output

4

Input

7 4 1 3 1 2 2 4 3

Output

6

Note

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

inputFormat

Input

The first line contains two integers n and x (1 ≤ n, x ≤ 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, ... a_n (1 ≤ a_i ≤ x).

outputFormat

Output

Print the number of pairs 1 ≤ l ≤ r ≤ x such that f(l, r) is sorted in non-descending order.

Examples

Input

3 3 2 3 1

Output

4

Input

7 4 1 3 1 2 2 4 3

Output

6

Note

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

样例

7 4
1 3 1 2 2 4 3

6

</p>