题目背景
可怜的小 Bronya，因为想不到好的 idea 气的又哭又闹，呜呜呜呜，好可怜啊。
题目描述
Bronya 想给《阿拉哈托·集训队互测》出个新的 DLC，但是想不到好的 idea。
她现在有 $n$ 个 idea，每个 idea 都有一个难度值 $a_i$，满足 $1 \le a_i \le m$。
她现在打算在这些 idea 中抽取一个 idea 作为最终 idea，她的抽取方式如下：
随机在 $\dfrac{n(n+1)}{2}$ 个区间中，等概率抽取一个编号区间 $[l,r]$，然后再在 $[1,m]$ 中等概率抽取一个整数作为难度上限 $lim$，
然后 Bronya 会在所有满足 $i \in [l,r], a_i \le lim$ 的 $i$ 中选一个 $a_i$ 最大的 $i$ 作为 $x$。
此时 $a_x$ 会作为最终的难度值，若这样的 $x$ 不存在，那最终的难度值为 $0$。
Bronya 想知道最终难度值的期望，请你帮帮可爱的她。
由于期望是高贵的 $10$ 级算法，小 Bronya 不会，所以请你输出期望乘以 $\dfrac{n \times (n+1) \times m}{2}$ 的值。
输入格式
第一行两个整数 $n, m$，分别表示 idea 的数量和难度值的上限。
第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个 idea 的难度值。
输出格式
一行一个整数 $ans$，表示最终难度值的期望乘以 $\dfrac{n \times (n+1) \times m}{2}$ 之后的值。
样例输入
3 4
1 1 4样例输出
30样例输入
10 20
5 19 3 14 2 8 18 7 1 5样例输出
7535样例解释
考虑最后选出的区间有 $[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]$ 六种可能。
其难度值期望分别是 $1,1,\frac{7}{4},1,\frac{7}{4},1$，则最后的答案为 $\dfrac{1+1+\frac{7}{4}+1+\frac{7}{4}+1}{6} \times 6 \times 4 = 30$
数据范围
对于所有测试点，$1 \le n \le 1 \times 10^6, 1 \le m \le 1 \times 10^9$。
- Subtask 1 (5pts): $n \le 500$
- Subtask 2 (5pts): $n \le 4000$，依赖 Subtask 1。
- Subtask 3 (5pts): $m \le 2$。
- Subtask 4 (20pts): $m \le 50$，依赖 Subtask 3。
- Subtask 5 (10pts): 保证 $a_i$ 在 $[1,m]$ 中随机生成，$n \le 5 \times 10^5$。
- Subtask 6 (20pts): $n \le 10^5$，依赖 Subtask 1,2。
- Subtask 7 (35pts): 无限制，依赖 Subtask 1,2,3,4,5,6。