//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=1000*1007;

int n, m;
int tab[nax];

vector <pii> pref[nax];
vector <pii> suf[nax];
int cal[nax];

map <int,vector <pii>> mapa;

ll wyn;

ll fen[nax];

void pisz(int v, ll w)
{
	v+=nax/2;
	for (int i=v; i; i-=(i&(-i)))
		fen[i]+=w;
}

ll czyt(int v)
{
	v+=nax/2;
	ll ret=0;
	for (int i=v; i<nax; i+=(i&(-i)))
		ret+=fen[i];
	return ret;
}

int scal[nax];
int tyl[nax];

void lacz(vector <pii> &wek)
{
	sort(wek.begin(), wek.end());
	vector <pii> pom;
	for (pii i : wek)
	{
		if (pom.empty() || pom.back().first!=i.first)
			pom.push_back({i.first, 0});
		pom.back().second+=i.second;
	}
	wek=pom;
}

void biegnij(int v, vector <pii> wek)
{
	debug() << v << " " << wek;
	int k=wek.size();
	scal[0]=0;
	for (int i=0; i<k; i++)
	{
		if (scal[i]==-1 || cal[wek[i].first]==-1)
			scal[i+1]=-1;
		else
			scal[i+1]=scal[i]+cal[wek[i].first];
	}
	tyl[k]=0;
	for (int i=k-1; i>=0; i--)
	{
		if (tyl[i+1]==-1 || cal[wek[i].first]==-1)
			tyl[i]=-1;
		else
			tyl[i]=tyl[i+1]+cal[wek[i].first];
	}
	
	int c=0;
	vector <pii> kum;
	for (int i=0; i<k; i++)
	{
		for (pii j : pref[wek[i].first])
			wyn+=czyt(m-(j.first+c))*j.second;
		c+=cal[wek[i].first];
		if (cal[wek[i].first]==-1)
		{
			for (pii j : kum)
				pisz(j.first, -j.second);
			kum.clear();
			c=0;
		}
		for (pii j : suf[wek[i].first])
		{
			pisz(j.first-c, j.second);
			kum.push_back({j.first-c, j.second});
		}
	}
	for (pii j : kum)
		pisz(j.first, -j.second);
	kum.clear();
	
	vector <pii> npref, nsuf;
	for (int i=0; i<k; i++)
	{
		if (scal[i]==-1)
			continue;
		for (pii j : pref[wek[i].first])
		{
			//~ debug() << i << " " << j << " " << scal[i];
			int x=j.first+scal[i];
			if (x>=m)
				npref.push_back({x/m, j.second});
		}
	}
	for (int i=k-1; i>=0; i--)
	{
		if (tyl[i]==-1)
			continue;
		for (pii j : suf[wek[i].first])
		{
			int x=j.first+tyl[i+1];
			if (x>=m)
				nsuf.push_back({x/m, j.second});
		}
	}
	
	//~ debug() << npref << " " << nsuf;
	lacz(npref);
	lacz(nsuf);
	//~ exit(0);
	int ncal=scal[k];
	
	debug() << "  " << ncal << " " << npref << " " << nsuf << " " << imie(wyn);
	//~ exit(0);
	
	if (!npref.empty() || !nsuf.empty() || ncal>=m)
	{
		pref[wek[0].first]=npref;
		suf[wek[0].first]=nsuf;
		cal[wek[0].first]=ncal/m;
		if (ncal<m)
			cal[wek[0].first]=-1;
		mapa[v+1].push_back({wek[0].first, wek.back().second});
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++)
		scanf("%d", &tab[i]);
	
	for (int i=1; i<=n; i++)
	{
		pref[i].push_back({1, 1});
		suf[i].push_back({1, 1});
		cal[i]=1;
		mapa[tab[i]].push_back({i, i});
	}
	for (auto i : mapa)
	{
		sort(i.second.begin(), i.second.end());
		vector <pii> pom;
		for (pii j : i.second)
		{
			if (!pom.empty() && pom.back().second+1!=j.first)
			{
				biegnij(i.first, pom);
				pom.clear();
			}
			pom.push_back(j);
		}
		biegnij(i.first, pom);
	}
	
	
	printf("%lld\n", wyn+n);
	return 0;
}


Measured memory_bytes: 84084