← 返回题目列表

Codeforces · 1110/D

D. 宗马

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

您正在玩 Jongmah 游戏。您不需要了解规则来解决这个问题。您手中有 $$$n$$$ 牌。每个图块上都写有一个介于 $$$1$$$ 和 $$$m$$$ 之间的整数。

要赢得比赛,您需要组成一定数量的三元组。每个三元组由三个图块组成,使得图块上写的数字要么全部相同,要么连续。例如,$$$7, 7, 7$$$ 是有效的三元组,$$$12, 13, 14$$$ 也是有效的三元组,但 $$$2,2,3$$$ 或 $$$2,4,6$$$ 则不是。您只能使用手中的牌组成三连。每个图块最多可用于一个三元组。

要确定您距离胜利有多近,您需要知道您手中的牌最多可以组成三连数。

输入

第一行包含两个整数整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^6$$$) – 你手中的牌数量和牌类型的数量。

第二行包含整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$),其中 $$$a_i$$$ 表示第 $$$i$$$ 块上写入的数字。

输出

打印一个整数:可以组成的三元组的最大数量。

示例

输入 #1

10 6
2 3 3 3 4 4 4 5 5 6

输出 #1

3

输入 #2

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

输出 #2

3

输入 #3

13 5
1 1 5 1 2 3 3 2 4 2 3 4 5

输出 #3

4

注意

在第一个示例中,我们有图块 $$$2, 3, 3, 3, 4, 4, 4, 5, 5, 6$$$。我们可以通过以下方式形成三个三元组:$$$2, 3, 4$$$; $$$3, 4, 5$$$; $$$4、5、6$$$。由于只有 $$$10$$$ 块,我们无法形成 $$$4$$$ 三元组,所以答案是 $$$3$$$。

在第二个示例中,我们有图块 $$$1$$$、$$$2$$$、$$$3$$$($$$7$$$ 次)、$$$4$$$、$$$5$$$($$$2$$$ 次)。我们可以如下形成 $$$3$$$ 三元组:$$$1, 2, 3$$$; $$$3, 3, 3$$$; $$$3、4、5$$$。可以证明,形成 $$$4$$$ 三元组是不可能的。