#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const int inf = 1e9 + 7;
long long n, m;
int l[maxn], r[maxn];
int a[maxn];
set<int> s;
vector<pair<long long, long long> > g[maxn];
int cnt = 0;
vector<pair<long long, long long> > ans;
bool cmp(pair<long long, long long> x, pair<long long, long long> y) {
  if (x.first != y.first)
    return x.first < y.first;
  else
    return x.second < y.second;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    s.insert(a[i]);
  }
  for (int i = 1; i <= 1e6; i++) l[i] = n + 1;
  for (int i = 1; i <= n; i++) {
    r[a[i]] = max(r[a[i]], i);
    l[a[i]] = min(l[a[i]], i);
  }
  set<int>::iterator iter;
  iter = s.begin();
  int x = l[*iter], y = r[*iter];
  iter++;
  for (; iter != s.end(); iter++) {
    int to = *iter;
    if (l[to] > y) {
      g[cnt].push_back(make_pair(x, y));
      x = l[to];
      y = r[to];
    } else {
      g[cnt++].push_back(make_pair(x, y));
      x = l[to];
      y = r[to];
    }
  }
  g[cnt].push_back(make_pair(x, y));
  if (cnt == 0) {
    long long sum = ((1LL + m) * m) / 2LL;
    cout << sum << endl;
    return 0;
  }
  for (int i = 0; i < g[0].size(); i++) {
    pair<long long, long long> tmp = g[0][i];
    int rr = tmp.second;
    int x = 0, y = g[cnt].size() - 1;
    while (y >= x) {
      int mid = (x + y) >> 1;
      if (g[cnt][mid].first > rr) {
        y = mid - 1;
      } else {
        x = mid + 1;
      }
    }
    long long lpos = i == g[0].size() - 1 ? g[1][0].first : g[0][i + 1].first;
    long long rpos = x == 0 ? g[cnt - 1][g[cnt - 1].size() - 1].second
                            : g[cnt][x - 1].second;
    if (a[lpos] <= a[rpos]) ans.push_back(make_pair(a[lpos], a[rpos]));
  }
  for (int i = 0; i < g[cnt].size(); i++) {
    pair<long long, long long> tmp = g[cnt][i];
    int rr = tmp.first;
    int x = 0, y = g[0].size() - 1;
    while (y >= x) {
      int mid = (x + y) >> 1;
      if (g[0][mid].second < rr) {
        x = mid + 1;
      } else {
        y = mid - 1;
      }
    }
    x = y;
    long long rpos = i == 0 ? g[cnt - 1][g[cnt - 1].size() - 1].second
                            : g[cnt][i - 1].second;
    long long lpos = x == g[0].size() - 1 ? g[1][0].first : g[0][x + 1].first;
    if (a[lpos] <= a[rpos]) ans.push_back(make_pair(a[lpos], a[rpos]));
  }
  long long sum = 0;
  sort(ans.begin(), ans.end(), cmp);
  for (int i = 0; i < ans.size(); i++) {
    if (i == 0) {
      sum += 1LL * ans[i].first * (m - ans[i].second + 1LL);
    } else {
      if (ans[i].second < ans[i - 1].second) {
        sum -= 1LL * ans[i - 1].first * (m - ans[i - 1].second + 1LL);
        sum += 1LL * ans[i].first * (m - ans[i].second + 1LL);
      } else
        sum +=
            1LL * (ans[i].first - ans[i - 1].first) * (m - ans[i].second + 1LL);
    }
  }
  cout << sum << endl;
  return 0;
}
