Background

Luogu’s testdata are only for non-official community communication and are not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

In the shopping mall on Xixi Aifu Island, there are many stores and a wide variety of products. To help visitors quickly choose the product they want within their budget, the IT department decides to develop a product retrieval system. For any given budget $x$, it should query the most expensive product whose price is within the budget range ($\leq x$). If no product meets the budget requirement, it will recommend a customized souvenir from Xixi Aifu Island that can be collected for free.

Assume there are $n$ products in the mall, and their prices from low to high are $A_1, A_2 \cdots A_n$. Then the process of retrieving a product based on budget $x$ can be abstracted as the following sequence query problem.

$A = [A_0, A_1, A_2, \cdots, A_n]$ is a sequence of $n + 1$ integers in the range $[0, N)$, satisfying $0 = A_0 < A_1 < A_2 < \cdots < A_n < N$. (This definition implies that $n$ must be less than $N$.)

Based on the sequence $A$, for any integer $x$ in the range $[0, N)$, define the query $f(x)$ as: the index of the largest integer in sequence $A$ that is less than or equal to $x$. Specifically, there are two cases:

1. There exists an index $0 \leq i < n$ such that $A_i \leq x < A_{i+1}$.

In this case, all numbers in $A$ from $A_0$ to $A_i$ are less than or equal to $x$. The largest is $A_i$, whose index is $i$, so $f(x) = i$.

2. $A_n \leq x$.

In this case, all numbers in $A$ are less than or equal to $x$. The largest is $A_n$, so $f(x) = n$.

Let $sum(A)$ denote the sum of $f(0)$ to $f(N - 1)$, that is:

$$\begin{aligned} sum(A) = \sum_{i=0}^{N-1} f(i) = f(0) + f(1) + f(2) + \cdots + f(N - 1) \end{aligned}$$

Given the sequence $A$, compute $sum(A)$.

Input Format

Read input from standard input.

The first line contains two positive integers $n$ and $N$, separated by spaces.

The second line contains $n$ integers $A_1, A_2, \cdots, A_n$, separated by spaces.

Note that $A_0$ is fixed as $0$, so the input does not include $A_0$.

Output Format

Write output to standard output.

3 10
2 5 8

15

9 10
1 2 3 4 5 6 7 8 9

45

Hint

Sample 1 Explanation

$A = [0, 2, 5, 8]$

$i$	0	1	2	3	4	5	6	7	8	9
$f(i)$	0		1			2			3

As shown in the table above, $sum(A) = f(0) + f(1) + \cdots + f(9) = 15$.

Considering that $f(0) = f(1)$, $f(2) = f(3) = f(4)$, $f(5) = f(6) = f(7)$, and $f(8) = f(9)$, you can also compute $sum(A)$ using the following expression:

$$\begin{aligned} sum(A) = f(0) \times 2 + f(2) \times 3 + f(5) \times 3 + f(8) \times 2 \end{aligned}$$

Subtasks

$50\%$ of the testdata satisfy $1 \leq n \leq 200$ and $n < N \leq 1000$;
all testdata satisfy $1 \leq n \leq 200$ and $n < N \leq 10^7$.

Hint

If there exists an interval $[i, j)$ such that $f(i) = f(i+1) = \cdots = f(j-1)$, using multiplication $f(i) \times (j - i)$ instead of adding $f(i)$ to $f(j-1)$ one by one may greatly improve the algorithm efficiency.

Translated by ChatGPT 5