Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Range Deleting

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Input

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

Output

Print the number of pairs $$$1 \le l \le r \le 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)$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/28/2021 18:59:21 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|