← 返回题目列表

Codeforces · 609/B

B. 最好的礼物

中文机器翻译题面 查看原题

下周是艾米丽的生日,杰克决定给她买一份礼物。他知道她喜欢书籍,所以他去了当地的书店,那里有 n 本书在售,涉及 m 种类型中的一种。

在书店里,杰克决定买两本不同类型的书。

根据商店中出售的书籍类型,找出杰克可以为艾米丽选择两本不同类型书籍的选项数量。如果选项在至少一本书中有所不同,则被视为不同。

这些书籍按其类型索引给出。流派编号从 1 到 m。

输入

第一行包含两个正整数 n 和 m (2 ≤ n ≤ 2·105, 2 ≤ m ≤ 10) — 书店中的书籍数量和流派数量。

第二行包含序列 a1, a2, ..., an,其中 ai (1 ≤ ai ≤ m) 等于第 i 本书的类型。

保证每种类型至少有一本该类型的书。

输出

打印唯一的整数 - 杰克可以选择书籍的方式数。

保证答案不超过值2·109。

示例

输入 #1

4 3
2 1 3 1

输出 #1

5

输入 #2

7 4
4 2 3 1 2 4 3

输出 #2

18

注意

第一个测试样本的答案等于 5,Sasha 可以选择:

1.第一本书和第二本书,
2.第一本书和第三本书,
3.第一本书和第四本书,
4.第二本书和第三本书,
5.第三、四本书。