#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 std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,l,a[200005];
vector<int>za;
vector<int>pos[200005];

bool in[200005];
int par[200005][2],ran[200005];
void init(){ for(int i=0;i<200005;i++) par[i][0] = par[i][1] = i; }
int find(int x,int a){
	if(x == par[x][a]) return x;
	else return par[x][a] = find(par[x][a],a); 
}
void unite(int x,int y){
	x = find(x,0); y = find(y,0);
	if(x != y){
		if(x < y) par[y][0] = x;
		else par[x][0] = y;
	}
	x = find(x,1); y = find(y,1);
	if(x != y){
		if(x > y) par[y][1] = x;
		else par[x][1] = y;
	}
}

map<P,vector<P>>dp;
map<P,int>mx;
vector<P>query[200005];
ll ans;
pair<pair<vector<int>,vector<int>>,int>rec(int L,int R){
	if(L > R){
		vector<int>vi; vi.pb(1);
		return mp(mp(vi,vi),-100);
	}
	vector<pair<pair<vector<int>,vector<int>>,int>>ret;
	vector<vector<int>>ruirui;

	SORT(dp[mp(L,R)]);
	vector<int>rui,rui2;
	int cur_v = 0, cur_v2 = 0;
	vector<int>forbid;
	for(auto x:dp[mp(L,R)]){
		ret.pb(rec(x.fi,x.sc));
		int dif = mx[mp(L,R)]-ret.back().sc;
		ll dv = 1;
		rep(q,dif) { dv = dv*l; if(dv >= mod) { dv = mod; break; }}
		int DV = (int)(dv);
		cur_v += (ret.back().fi.fi.size()-1) / dv + 1;
		vector<int>hoge; int sum = 0;
		for(int i=0;i<ret.back().fi.fi.size();i++){
			sum += ret.back().fi.fi[i];
			hoge.pb(sum);
		}
		for(int i=0;i<ret.back().fi.fi.size();i++){
			if(i && i<dv) continue;
			if(i==0 && ret.size() >= 2) continue;
			cur_v2 += ret.back().fi.fi[i];
		}
		if(ret.back().fi.fi.size() >= 2 && ret.back().fi.fi.size() <= dv && ret.size() >= 2) forbid.pb(ret.size()-2);
		cur_v2 ++;
		rui.pb(cur_v);
		rui2.pb(cur_v2);
		ruirui.pb(hoge);
	}
	//if(L == 1 && R == 8) cout << ret.size() << " " << rui.size() << " " << rui2.size() << " " << ruirui.size() << endl;
	assert(rui.size() >= 1 && rui2.size() >= 1);
	rui.back()--; rui2.back()--;
	int nxt = 0;
	for(int i=0;i<ret.size()-1;i++){
		int dif = mx[mp(L,R)]-ret[i].sc;
		ll dv = 1;
		rep(q,dif) { dv = dv*l; if(dv >= mod) { dv = mod; break; }}
		int DV = (int)(dv);
		nxt = max(nxt,i);
		for(int j=ret[i].fi.sc.size()-1;j>=0;j--){
			if(j && j<dv) continue;
			ll coef = ret[i].fi.sc[j];
			int num = j/dv+1;
			while(nxt < rui.size() && rui[nxt]-rui[i]+num < l) nxt++;
			//if(L==1&&R==8) cout << i << " " << j << " " << nxt << endl;
			if(nxt == rui.size()) break;
			if(nxt == i){
				int a = POSL(forbid,i);
				int x = rui2.size()-1;
				if(a < forbid.size()) x = forbid[a];
				ans += 1LL * coef * (rui2[x]-rui2[i]+1);
			}
			else{
				int a = POSL(forbid,i);
				int x = rui2.size()-1;
				if(a < forbid.size()) x = forbid[a];
				//cout << L << R << x << nxt << endl;
				if(x >= nxt) ans += 1LL * coef * (rui2[x]-rui2[nxt]+1);
				//cout<<ans<<endl;
				int cur = rui[nxt-1]-rui[i]+num; assert(l > cur);
				int need = l-cur;
				int dif = mx[mp(L,R)]-ret[nxt].sc;
		ll dvv = 1;
		rep(q,dif) { dvv = dvv*l; if(dvv >= mod) { dvv = mod; break; }}
		
				ll beg = min(1LL*mod,1LL*need*dvv); 
				//if(L==1 && R==8) cout << need << " " << dv << " " << i << " " << j << endl;
				if(beg < ret[nxt].fi.fi.size()) ans += 1LL * coef * (ruirui[nxt][ret[nxt].fi.fi.size()-1] - ruirui[nxt][beg-1]);
			}
			//cout<<ans<<endl;
		}
	}
	vector<int>le,ri;
	for(int i=0;i<ret.size();i++){
		int dif = mx[mp(L,R)]-ret[i].sc;
		ll dv = 1;
		rep(q,dif) { dv = dv*l; if(dv >= mod) { dv = mod; break; }}
		int DV = (int)(dv);
		assert(ret[i].fi.fi.size());
		int num = (ret[i].fi.fi.size()-1) / dv;
		if(num == 0){
			le.pb(1);
			if(ret[i].fi.fi.size() >= 2) break;
		}
		else{
			le.pb(1);
			int cnt = 0;
			for(int ii=dv;ii<ret[i].fi.fi.size();ii++){
				cnt += ret[i].fi.fi[ii];
				if(ii%dv == dv-1 || ii+1 == ret[i].fi.fi.size()){
					le.pb(cnt); cnt = 0;
				}
			}
		}
	}
	for(int i=ret.size()-1;i>=0;i--){
		int dif = mx[mp(L,R)]-ret[i].sc;
		ll dv = 1;
		rep(q,dif) { dv = dv*l; if(dv >= mod) { dv = mod; break; }}
		int DV = (int)(dv);
		int num = (ret[i].fi.sc.size()-1) / dv;
		assert(ret[i].fi.sc.size());
		if(num == 0){
			ri.pb(1);
			if(ret[i].fi.sc.size() >= 2) break;
		}
		else{
			ri.pb(1);
			int cnt = 0;
			for(int ii=dv;ii<ret[i].fi.sc.size();ii++){
				cnt += ret[i].fi.sc[ii];
				if(ii%dv == dv-1 || ii+1 == ret[i].fi.sc.size()){
					ri.pb(cnt); cnt = 0;
				}
			}
		}
	}
    /*cout << L << " " << R << " " << ans << endl; /*
	cout << "=======" << endl;
	rep(i,le.size()) cout << le[i] << " i " << endl;
	cout << "=======" << endl;
	rep(i,ri.size()) cout << ri[i] << " j " << endl;
	cout << "=======" << endl;
	cout << L << "  " << R << " " << ans << endl;*/
	return mp(mp(le,ri),mx[mp(L,R)]);
}
int main(){
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		za.pb(a[i]);
	}
	init();
	SORT(za); ERASE(za);
	for(int i=1;i<=n;i++){
		int x = POSL(za,a[i]);
		pos[x].pb(i);
	}
	for(int i=0;i<za.size();i++){
		for(int j=0;j<pos[i].size();j++){
			in[pos[i][j]] = 1;
		}
		for(int j=0;j<pos[i].size();j++){
			int x = pos[i][j];
			if(in[x-1]) unite(x-1,x);
			if(in[x+1]) unite(x,x+1);
		}
		set<int>S;
		for(int j=0;j<pos[i].size();j++){
			int hoge = find(pos[i][j],0);
			int hoge2 = find(pos[i][j],1);
			query[hoge].pb(mp(pos[i][j],hoge2));
			S.insert(hoge);
		}
		for(auto le:S){
			int pre = -1;
			rep(x,query[le].size()){
				if(pre == -1) pre = query[le][x].sc;
				else assert(pre == query[le][x].sc);
			}
			int ri = pre;
			assert(le <= ri);
			mx[mp(le,ri)] = za[i];
			dp[mp(le,ri)].pb(mp(query[le].back().fi+1,ri));
			for(int x=query[le].size()-1;x>=0;x--){
				int R = query[le][x].fi-1;
				int L = (x?query[le][x-1].fi+1:le);
				dp[mp(le,ri)].pb(mp(L,R));
			}
		}
		for(auto le:S) query[le].clear();
	}
	rec(1,n);
	cout << ans+n << endl;
}