#include <stdio.h>
#include <algorithm>
int a[100001],b[100001];
int n,k;
int main()
{
    FILE *fin,*fout;
    fin=fopen("calcule.in","r");
    fout=fopen("calcule.out","w");
    fscanf(fin,"%d %d",&n,&k);
    for(int i=0;i<n;i++) fscanf(fin,"%d",&a[i]);
    b[0]=a[0];
    int pos=1,nr;
    bool as=0;
    for(int i=2;i<=n;i++)
    {
            nr = std::lower_bound(b, b+pos, a[i]- 1) - b;
            if(b[nr]>=a[i])
            {
                        b[pos]=a[i];
                        pos++;
            }
            else
            {
                b[nr]=a[i];
            }
            nr=0;
    }
    b[0]=0;
    fprintf(fout,"%d",pos-1);
    for(int i=1;i<n;i++)
    {
            b[i]=0;
            a[i]+=a[i-1];
    }
    for(int i=0;i<n;i++)
    {
            a[i]%=3;
            b[a[i]]++;        
    }
    int s=0;
    s+=b[0]+b[0]*(b[0]-1)/2;
    for(int i=1;i<k;i++) s+=b[i]*(b[i]-1)/2;
    fprintf(fout,"\n%d",s);
}