606. Jongmah
0
Medium
You are participating in a game called Jongmah. Familiarity with the game rules is not necessary to solve this problem. You have a total of n tiles in your possession. Each tile is marked with an integer ranging from 1 to m.
To win the game, you must create a certain number of triples. A triple consists of three tiles, where the numbers on the tiles are either all the same or consecutive. For example, 7,7,7 is a valid triple, as is 12,13,14. However, 2,2,3 or 2,4,6 are not valid triples. You can only use the tiles in your possession to form triples, and each tile can only be used once.
To determine your progress towards victory, you want to determine the maximum number of triples you can form using the tiles in your possession.
Input Format
The first line contains two integers, n and m. These represent the number of tiles in your possession and the number of different tile types, respectively.
The second line contains n integers, a1,a2,...,an, where ai represents the number written on the i-th tile.
Output Format
Print a single integer: the maximum number of triples you can form.
Example
Input
10 6
2 3 3 3 4 4 4 5 5 6
Output
3
Constraints
1≤n,m≤106
1≤ai≤m
1≤ai≤m
Loading...
View Submissions
Console