Preparing NOJ

Range Deleting

2000ms 262144K

Description:

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.

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.

Sample Input:

 3 3 2 3 1 

Sample Output:

 4 

Sample Input:

 7 4 1 3 1 2 2 4 3 

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

Info

CodeForces

Provider CodeForces

Origin Educational Codeforces Round 65 (Rated for Div. 2)

Code CF1167E

Tags

binary searchcombinatoricsdata structurestwo pointers

Submitted 13

Passed 7

AC Rate 53.85%

Date 07/21/2019 13:39:43

Related

Nothing Yet