CodeForces-1167E-Range Deleting

Description

You are given an array consisting of \(n\) integers \(a_1, a_2,\dots,a_n\) and an integer \(x\). It is guaranteed that for every \(i\), \(1 \le a_i \le x\).

Let's denote a function \(f(l,r)\) which erases all values such that \(l \le a_i \le r\) from the array \(a\) and returns the resulting array. For example, if \(a=[4,1,1,4,5,2,4,3]\), then \(f(2,4)=[1,1,5]\).

Your task is to calculate the number of pairs \((l,r)\) such that \(1 \le l \le r \le x\) and \(f(l, r)\) is sorted in non-descending order. Note that the empty array is also considered sorted.

Input

The first line contains two integers \(n\) and \(x\) \((1 \le n, x \le 10^6)\) — the length of array a and the upper limit for its elements, respectively.

The second line contains \(n\) integers \(a_1, a_2,\dots a_n\) \((1 \le a_i \le x)\).

Output

Print the number of pairs \(1 \le l \le r \le x\) such that \(f(l,r)\) is sorted in non-descending order.

Examples

Input

3 3
2 3 1

Output

4

Input

7 4
1 3 1 2 2 4 3

Output

6

Solution

找到所有可能的逆序对右端点，排序去重，结果记为\(\text{less_value}\)

找到所有可能的逆序对左端点，排序去重，结果记为\(\text{greater_value}\)

枚举\(l\)，当\(1 \le l \le \text{less_value}[0]\)时，\(r\)的取值是\(\text{less_value.back()}\)到\(x\)；当\(\text{less_value[0]} \lt l \le \text{greater_value[0]}\)时，\(r\)不但要大于\(\text{less_value.back()}\)，还需要大于所有比\(r\)小的逆序对右端点对应的最大左端点。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  int n, x;
  scanf("%d%d", &n, &x);
  vector<int> a(n), max_greater_value(x + 1, 0), less_value;
  for (int i = 0; i < n; ++i)
    scanf("%d", &a[i]);
  for (int i = 0, mx = 0; i < n; ++i) {
    if (a[i] < mx) {
      max_greater_value[a[i]] = mx;
      less_value.push_back(a[i]);
    }
    mx = max(mx, a[i]);
  }
  sort(less_value.begin(), less_value.end());
  less_value.resize(unique(less_value.begin(), less_value.end()) - less_value.begin());
  if (less_value.size() == 0) {
    printf("%I64d\n", (ll)x * (x + 1) / 2);
    return 0;
  }
  int min_greater_value = x;
  for (int i = n - 1, mn = x + 1; i >= 0; --i) {
    if (a[i] > mn) {
      min_greater_value = min(min_greater_value, a[i]);
    }
    mn = min(mn, a[i]);
  }
  ll ans = (ll)less_value[0] * (x - less_value.back() + 1);
  for (int i = less_value[0] + 1, p = 0, mx = max(less_value.back(), max_greater_value[less_value[0]]);
      i <= min_greater_value; ++i) {
    while (p + 1 < less_value.size() && less_value[p + 1] < i) {
      ++p;
      mx = max(max_greater_value[less_value[p]], mx);
    }
    ans += (x - mx + 1);
  }
  printf("%I64d\n", ans);
  return 0;
}