#P18190. Train Seats

Train Seats

Train Seats

有 MM 把椅子排成一行,从左到右编号为 1,2,…,M1,2,\ldots,M。有 NN 个人,编号为 1,2,…,N1,2,\ldots,N。第 ii 个人将坐在椅子 AiA_i 上,不同的人所坐的椅子互不相同。

最初所有椅子都没有人。所有人按照某个顺序依次入座。

当一个人入座时,设其左边最近的已有人入座的椅子编号为 LL,右边最近的已有人入座的椅子编号为 RR。如果左边没有已入座的人,令 L=0L=0;如果右边没有已入座的人,令 R=M+1R=M+1。这个人获得的分数为 R−LR-L。

共有 N!N! 种入座顺序。求所有人分数总和的最大可能值。

输入格式

第一行两个整数 N,MN,M。

第二行 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

输出格式

输出一个整数,表示最大的总分。

数据范围

  • 1≤N≤2×1051\le N\le2\times10^5;
  • N≤M≤109N\le M\le10^9;
  • 1≤Ai≤M1\le A_i\le M;
  • 当 i≠ji\ne j 时,Ai≠AjA_i\ne A_j;
  • 所有输入均为整数。

输入中的 AiA_i 不保证已经排序。

样例 1

输入

3 10
3 7 10

输出

28

例如,依次让第 3、1、2 个人入座:

  • 第 3 个人入座时,L=0,R=11L=0,R=11,得分为 1111;
  • 第 1 个人入座时,L=0,R=10L=0,R=10,得分为 1010;
  • 第 2 个人入座时,L=3,R=10L=3,R=10,得分为 77。

总分为 11+10+7=2811+10+7=28,可以证明这已是最大值。

样例 2

输入

5 20
3 10 11 14 17

输出

73

样例 3

输入

10 1000000000
136909656 243332691 643531997 505919307 43553384 657638276 57213246 179732866 357373203 182482400

输出

7649951260