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 32 3 1

Output

4

Input

7 41 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 
    
     using namespace std;using ll = long long;int main() {  int n, x;  scanf("%d%d", &n, &x);  vector
     
       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;}