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 Provider CodeForces

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