D. Jongmah cf1110

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
long long dp[1000010][3][3];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        a[tmp]++;
    }
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0][0]=0;
    for(int i=1;i<=m;i++)
    {
        for(int x=0;x<=2;x++)//表示第i个数字能提供x个数字为a-1,a,a+1形式的子段 
        {
            for(int y=0;y<=2;y++)//表示i个数字能提供y个数字为a,a+1,a+2个子段 
            {
                for(int z=0;z<=2;z++)//x,y,z的顺序不用管，因为总会遍历x,y,z的所有组合，并且i-1层的状态已经算出，所以总是转移总是合法的 
                {
                    if(x+y+z>a[i])
                       continue;
                    dp[i][x][y]=max(dp[i][x][y],dp[i-1][z][x]+(a[i]-x-y-z)/3+z);
                }
            }
        }
    }
    printf("%lld
",dp[m][0][0]);
}