P15546 「Stoi2037」七里香

> 雨下整夜 我的爱溢出就像雨水 > 院子落叶 跟我的思念厚厚一叠 > 几句是非 也无法将我的热情冷却 > 你出现在我诗的每一页 > 雨下整夜 我的爱溢出就像雨水 > 窗台蝴蝶 像诗里纷飞的美丽章节 > 我接着写 把永远爱你写进诗的结尾 > 你是我唯一想要的了解 > ——《七里香》

**本题提供形式化题意，可选择略过原版题面阅读形式化题意。** Narika 要编写一本共有 $n$ 页的诗集，每页有 $k$ 行。她会对诗的所有行进行编号，第 $i$ 页第 $j$ 行的编号为 $(i-1)k+j$。 她已经构想了 $n$ 页诗歌内容，每一页都有一行包含一个关键词，她想到的第 $i$ 页内容中关键词在第 $a_i$ 行。现在她要将这些诗页重新排序，使得第 $i$ 页中关键词在第 $a_i'$ 行，满足对于任意 $1\le x\le k$，$x$ 在 $a_i$ 中出现次数与在 $a_i'$ 中出现次数相同。 她认为两个关键词靠得太近不够优美，因此她定义在排序后的诗歌中，一对关键词之间产生的优美度为两个关键词所在行的编号之差的绝对值。例如第 $4,9$ 行有关键词，则它们产生的优美度为 $9-4=5$。 由于诗歌会经常被节选出片段来朗诵，她定义诗歌的一个片段是排序后的诗歌的第 $l$ 到 $r$ 页，其中 $1\le l

第一行输入两个整数表示 $n,k$。 第二行输入 $n$ 个整数表示 $a_1,\dots,a_n$。

输出一行一个整数表示排序后诗歌优美度的最大可能值。

#### 样例 1 解释 若她排序后的诗歌第 $1,2,3$ 页中关键词分别在第 $1,2,3$ 行，则编号分别为 $0\times3+1=1,1\times3+2=5,2\times3+3=9$。所有可能节选片段及其优美度为： + 第 $1$ 到 $2$ 页，优美度为 $5-1=4$； + 第 $1$ 到 $3$ 页，优美度为 $(5-1)+(9-1)+(9-5)=16$； + 第 $2$ 到 $3$ 页，优美度为 $9-5=4$。 故诗歌的优美度为 $4+16+4=24$，可以证明这是最大可能值。 #### 数据范围与限制 对于 $10\%$ 的数据，保证 $n\le6$； 对于 $30\%$ 的数据，保证 $n\le100$； 对于 $70\%$ 的数据，保证 $n\le10^3$； 对于所有数据，保证 $1\le n\le10^5$，$1\le a_i\le k\le 10^6$。