#AT0020. [PA2021] Oranżada

[PA2021] Oranżada

题目描述

有一排共 nn 瓶橙汁,其中第 ii 瓶的品牌为 aia_i

你可以花费 11 个单位的的代价交换两瓶相邻的橙汁。

求最小代价使得最左边 kk 瓶橙汁品牌两两不同。

输入格式

第一行,两个整数 n,kn, k

第二行,nn 个整数 a1,a2,,ana_1, a_2, \cdots, a_n

输出格式

一行,一个整数,若有解,输出最小代价;否则,输出 1-1

5 3
3 3 3 1 2
4
3 2
1 1 1
-1

提示

样例 #1 解释

最优方案为先交换位置 3344 的瓶子、再交换位置 4455 的瓶子,接着交换位置 2233 的瓶子,最后交换位置 3344 的瓶子,共 44 次操作。

样例 #2 解释

显然无解。

数据范围

对于 100%100\% 的数据,1k,ain5×1051 \leq k, a_i \leq n \leq 5 \times 10^5