Вы играете в игру «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$$$-й кости.
Выведите одно целое число — максимально возможное количество троек, которое вы можете составить.
10 6
2 3 3 3 4 4 4 5 5 6
3
12 6
1 5 3 3 3 4 3 5 3 2 3 3
3
13 5
1 1 5 1 2 3 3 2 4 2 3 4 5
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$$$ тройки нельзя.
| Codeforces Global Round 1 |
|---|
| Закончено |
