//2019.8.23 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f
#define unl __int128
#define eps 5.6e-8
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
typedef pair<int,int> Pair;
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define ull unsigned LL
#define gc getchar
//inline char gc() {
//    static char buf[100000],*p1,*p2;
//    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
inline int read() {
    res s=0,ch=gc();
    while(ch<'0'||ch>'9')ch=gc();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s;
}
//inline int read() {
//    res s=0,ch=gc(),w=1;
//    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s*w;
//}
//inline LL Read() {
//    RG LL s=0;
//    res ch=gc();
//    while(ch<'0'||ch>'9')ch=gc();
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s;
//}
//inline LL Read() {
//    RG LL s=0;
//    res ch=gc(),w=1;
//    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s*w;
//}
//inline void write(RG unl x){
//    if(x>10)write(x/10);
//    putchar(int(x%10)+'0');
//}
inline void swap(res &x,res &y) {
    x^=y^=x^=y;
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//clock_t start=clock();
//inline void ck(){
//    if(1.0*(clock()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
const int N=2e5+10;
namespace MAIN{
    int n,l;
    int a[N];
    Pair b[N];
    LL ans;
    typedef pair<Pair,Pair> pii;
    vector<pii> f,g;
    vector<Pair> tmp,F,G;
    inline LL calc(const RG vector<Pair> &A){
        RG LL ret=0,sum=0;
        for(res i=0,j=l-1,sz=int(A.size()-1);j<=sz;i++,j++)sum+=A[i].fi,ret+=sum*A[j].se;
        return ret;
    }
    inline void MAIN(){
        n=read(),l=read();
        for(res i=1;i<=n;i++)a[i]=read(),b[i]=mp(a[i],i);
        sort(b+1,b+1+n),ans=n;
        res pos=1,val=0;
        while(233){
//            res val=0;
//            printf("%d\n",int(f.size()));
            if(!f.size()){
//                puts("OK");
                if(pos>n)break;
                val=b[pos].fi;
            }
            else val++;
            while(val==b[pos].fi)f.pb(mp(mp(b[pos].se,b[pos].se),mp(1,1))),pos++;
//            printf("%d\n",pos);
            g.clear(),sort(f.begin(),f.end());
            for(res i=0,sz=int(f.size()-1);i<=sz;){
//                printf("%d\n",i);
                res j=i;
                while(j+1<=sz&&f[j+1].fi.fi==f[j].fi.se+1)j++;
//                printf("%d %d\n",i,j);
                res len=j-i+1,cnt=len/l;
//                printf("%d\n",cnt);
                if(cnt){
                    tmp.clear(),F.clear(),G.clear();
                    for(res k=i;k<=j;k++)tmp.pb(f[k].se);
//                    printf("%d\n",ans);
                    ans+=calc(tmp);
                    for(res k=1;k<=cnt;k++)F.pb(mp(f[i].fi.fi+k-1,(k==cnt)?f[j].fi.se:f[i].fi.fi+k-1)),G.pb(mp(0,0));
                    for(res k=i;k<=j;k++){
                        res tl=k-i+1,tr=j-k+1;
                        if(tl>=l)G[tl/l-1].se+=f[k].se.se;
                        if(tr>=l)G[cnt-tr/l].fi+=f[k].se.fi;
                    }
                    ans-=calc(G);
                    for(res k=0;k<cnt;k++)g.pb(mp(F[k],G[k]));
                }
//                printf("QAQ%d %d\n",i,j);
                i=j+1;

            }
            f=g;
        }
        printf("%lld\n",ans);
    }
}
int main(){
//    srand(19260817);
//    freopen("signin.in","r",stdin);
//    freopen("signin.out","w",stdout);
    MAIN::MAIN();
    return 0;
}

Measured memory_bytes: 10988