问题描述

西西艾弗岛的购物中心里店铺林立，商品琳琅满目。为了帮助游客根据自己的预算快速选择心仪的商品，IT 部门决定研发一套商品检索系统，支持对任意给定的预算 $x$，查询在该预算范围内（$\le x$）价格最高的商品。如果没有商品符合该预算要求，便向游客推荐可以免费领取的西西艾弗岛定制纪念品。

假设购物中心里有 $n$ 件商品，价格从低到高依次为 $A_1,A_2,\dots,A_n$，则根据预算 $x$ 检索商品的过程可以抽象为如下序列查询问题。

令 $A=[A_0,A_1,A_2,\dots,A_n]$ 是一个由 $n+1$ 个整数组成的序列，所有元素均在区间 $[0,N)$ 内，且满足

$$0=A_0 < A_1 < A_2 < \cdots < A_n < N.$$

（这个定义中蕴含了 $n$ 一定小于 $N$。）

基于序列 $A$，对于区间 $[0,N)$ 内任意整数 $x$，定义函数 $f(x)$ 为：序列 $A$ 中小于等于 $x$ 的整数里最大的数的下标。具体来说有以下两种情况：

• 若存在下标 $0\le i<n$ 满足 $A_i\le x < A_{i+1}$，则 $A_0,\dots,A_i$ 均 $\le x$，其中最大的为 $A_i$，因此 $f(x)=i$。
• 若 $A_n\le x$，则序列中所有数都 $\le x$，其中最大的为 $A_n$，因此 $f(x)=n$。

令

$$\text{sum}(A)=\sum_{i=0}^{N-1} f(i)=f(0)+f(1)+\cdots+f(N-1). $$

对于给定的序列 $A$，试计算 $\text{sum}(A)$。

输入格式

第一行包含用空格分隔的两个正整数 $n$ 和 $N$。

第二行包含 $n$ 个用空格分隔的整数 $A_1,A_2,\dots,A_n$。

注意 $A_0$ 固定为 $0$，因此输入数据中不包括 $A_0$。

输出格式

仅输出一个整数，表示 $\text{sum}(A)$ 的值。

输入样例 1

3 10
2 5 8

输出样例 1

15

输入样例 2

9 10
1 2 3 4 5 6 7 8 9

输出样例 2

45

说明

样例 1 解释：

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

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

因此 $\text{sum}(A)=15$。 也可观察到 $\text{sum}(A)=f(0)\times2 + f(2)\times3 + f(5)\times3 + f(8)\times2$ 。

数据范围

• $50\%$ 的测试数据满足 $1\le n\le 200$ 且 $n< N\le 1000$；
• 全部的测试数据满足 $1\le n\le 200$ 且 $n< N\le 10^7$。

提示

若存在区间 $[i,j)$ 满足 $f(i)=f(i+1)=\cdots=f(j-1)$，使用乘法运算 $f(i)\times (j-i)$ 代替将 $f(i)$ 到 $f(j-1)$ 逐个相加，或可大幅提高算法效率。