问题 D: 动物园(zoo)

问题 D: 动物园(zoo)

时间限制: 1 Sec  内存限制: 256 MB
提交: 101  解决: 42
[提交][状态][讨论版][命题人:]

题目描述

某动物园里有n个场馆和m种动物(m≤n)。

 n个场馆的编号分别用 1,2,3, . . , n表示;m种动物的编号分别用 1,2,3, . . , m表示。每一个 场馆中只饲养了一只动物,不同的场馆可能饲养着相同种类的动物。 

这个动物园的门票比较特殊,游客在购买门票时必须说明要参观的场馆的起止编号a和b (起止编号会打印到游客购买的门票上),代表游客只能参观动物园的第a个场馆至第b个 场馆(包含 a, b)里的动物,其他的场馆不能去。门票按一个场馆十元收费。 如果你购买的门票的起止场馆编号是 3 到 8,那么你需要花 60 元钱购买门票,只能观看 3,4,5,6,7,8 号场馆的动物。 小明希望看到动物园内所有种类的动物,同时小明是个非常节约的孩子,他希望花最少 的钱买门票。 请你帮小明计算:他最少需要花费多少钱买门票才能看到所有种类的动物(同 一种动物他可能不止看一个)。注意:小明只能买一张门票。

输入

第一行两个整数 n,m,分别表示动物园内的场馆数量及动物种类数量。

第二行是 x1 , x2 , . . . ,xn,其中xi表示第i个场馆中的动物种类

输出

一行一个整数 p,表示小明的门票费

样例输入

12 5
2 5 3 1 3 2 4 1 1 5 4 3

样例输出

60

提示


•对于 30% 的数据,有n≤ 200 ,m≤ 20。 



• 对于 60% 的数据,有 n≤ 1000 , m≤ 1000。 



• 对于 100% 的数据,有 1 ≤n≤ 10^6,1 ≤xi≤m≤ 2 × 10^3。 

[提交][状态]