#include<bits/stdc++.h>
using namespace std;
#define int __int128
int n,m;
int a[1000010];
int tot=0,lsh[1000010];
vector<int> vec[1000010];
int l[1000010],r[1000010];
void write(int x)
{
	if(x==0) return putchar('0'),void();
	int tot=0,dig[40];
	while(x!=0) dig[++tot]=x%10,x/=10;
	for(int i=tot; i>=1; --i) putchar(dig[i]+'0');
}
signed main()
{
	long long re; cin>>re,n=re,cin>>re,m=re;
	lsh[++tot]=m+1;
	for(int i=1; i<=n; ++i) cin>>re,a[i]=re,lsh[++tot]=a[i];
	sort(lsh+1,lsh+tot+1),tot=unique(lsh+1,lsh+tot+1)-lsh-1;
	for(int i=1; i<=n; ++i) vec[lower_bound(lsh+1,lsh+tot+1,a[i])-lsh].push_back(i);
	int sum=0;
	for(int i=1; i<=n; ++i) l[i]=1,r[i]=i,a[i]=tot,sum+=lsh[a[i]]*(i-l[i]+1)*(r[i]-i+1);
	int ans=0;
	for(int i=tot; i>=1; --i)
	{
		int sum1=sum;
		for(int j:vec[i])
		{
			for(int k=1; k<j; ++k)
			{
				sum-=lsh[a[k]]*(k-l[k]+1)*(r[k]-k+1);
				r[k]=min(r[k],j-1);
				sum+=lsh[a[k]]*(k-l[k]+1)*(r[k]-k+1);
			}
			for(int k=j+1; k<=n; ++k)
			{
				sum-=lsh[a[k]]*(k-l[k]+1)*(r[k]-k+1);
				l[k]=max(l[k],j+1);
				sum+=lsh[a[k]]*(k-l[k]+1)*(r[k]-k+1);
			}
		}
		for(int j=0; j<vec[i].size(); ++j)
		{
			int wz=vec[i][j];
			sum-=lsh[a[wz]]*(wz-l[wz]+1)*(r[wz]-wz+1);
			l[wz]=1,r[wz]=(j==vec[i].size()-1?n:vec[i][j+1]-1),a[wz]=i;
			sum+=lsh[a[wz]]*(wz-l[wz]+1)*(r[wz]-wz+1);
		}
		int sum2=sum;
		for(int j:vec[i]) sum2-=lsh[a[j]]*(j-l[j]+1)*(r[j]-j+1);
		int cnt=(n+1)*n/2,lst=0;
		for(int j:vec[i]) cnt-=(j-lst)*(j-lst-1)/2,lst=j;
		cnt-=(n-lst+1)*(n-lst)/2;
		ans+=lsh[i]*(sum1-sum2-cnt*lsh[i]);
//		cout<<"sum: "<<sum1<<' '<<sum2<<' '<<cnt<<' '<<ans<<'\n';
//		cout<<"a:\n";
//		for(int j=1; j<=n; ++j) cout<<lsh[a[j]]<<' '; cout<<'\n';
//		for(int j=1; j<=n; ++j) cout<<l[j]<<' '<<r[j]<<'\n';
	}
	write(ans);
	return 0;
}