3930: dark

dark.in/out

巴瓦鲁魔法图书馆需要照明。

为此Patchouli打算制作一批奥术灯，于是她找来了一串圣晶石。这串圣晶石有n块，每一块都含一种要素，第i块为ai。Patchouli可以任意取出若干段，将每一段圣晶石分别熔铸为一盏奥术灯。在一盏灯中，每种要素会提供1 Watt功率，维持一盏灯运作需要k Watt功率，剩下的功率将全部用于发光。如果一盏灯中圣晶石提供的功率小于等于k Watt那么它无法工作，不发光。也就是说，将[L,R]区间内的圣晶石熔铸为一盏灯产生的照明功率为max(M-K,0)，其中M为[L,R]区间内元素种类数。

Patchouli想知道用这串圣晶石制作的照明系统，照明功率之和最大为多少。

【样例解释】

最优方案不唯一

【数据规模与约定】

对于 30% 的数据： n ≤20;

对于 60% 的数据：n ≤ 2000;

对于 100% 的数据：k ≤ n ≤ 200000, ai ≤ n;

9 2
3 4 2 1 3 1 2 3 1

3