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



-----Note-----

In the first test case correct pairs are $(1, 1)$, $(1, 2)$, $(1, 3)$ and $(2, 3)$.

In the second test case correct pairs are $(1, 3)$, $(1, 4)$, $(2, 3)$, $(2, 4)$, $(3, 3)$ and $(3, 4)$.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

n,x=list(map(int,input().split()))
A=list(map(int,input().split()))

MIN_R=[A[-1]]
for a in A[:-1][::-1]:
    MIN_R.append(min(a,MIN_R[-1]))

MIN_R=MIN_R[::-1]

MAX=x

for i in range(n-1):
    if A[i]>MIN_R[i+1]:
        MAX=min(MAX,A[i])

MAX_L=[A[0]]
for a in A[1:]:
    MAX_L.append(max(a,MAX_L[-1]))

MIN=0
for i in range(1,n):
    if MAX_L[i-1]>A[i]:
        MIN=max(MIN,A[i])

NEED=[i for i in range(x+3)]

for i in range(n-1):
    if A[i]>MIN_R[i+1]:
        NEED[1]=max(NEED[1],MIN_R[i+1])
        NEED[MIN_R[i+1]+1]=max(NEED[MIN_R[i+1]+1],A[i])

for i in range(1,x+2):
    NEED[i]=max(NEED[i],NEED[i-1])

ANS=0

for i in range(1,MAX+1):
    ANS+=x-max(MIN,NEED[i])+1

    #print(i,ANS)

print(ANS)


n, x = map(int, input().split())
a = list(map(int, input().split()))

mi = [x + 1] * (x + 1)
ma = [0] * (x + 1)
trie = [0] * (1 << 23)
m = 4
trie[0] = x + 1
for i in a:
  at = 0
  mii = x + 1
  maa = 0
  for j in range(19, -1, -1):
    if (i & (1 << j)):
      if not trie[at + 3]:
        trie[at + 3] = m
        at = m
        trie[m] = i
        trie[m + 1] = i
        m += 4
      else:
        at = trie[at + 3]
        trie[at] = min(trie[at + 0], i)
        trie[at + 1] = max(trie[at + 1], i)
    else:
      if trie[at + 3]:
        mii = trie[trie[at + 3]]
        if not maa:
          maa = trie[trie[at + 3] + 1]
      if not trie[at + 2]:
        trie[at + 2] = m
        at = m
        trie[m] = i
        trie[m + 1] = i
        m += 4
      else:
        at = trie[at + 2]
        trie[at] = min(trie[at + 0], i)
        trie[at + 1] = max(trie[at + 1], i)
  mi[i] = min(mi[i], mii)
  ma[i] = max(ma[i], maa)

fi = 0
for i in range(x, 0, -1):
  if mi[i] != x + 1:
    fi = i
    break

ans = 0
g = x + 1
for i in range(1, x + 1):
  ans += x - max(i, fi) + 1
  if i == g:
    break
  fi = max(fi, ma[i])
  g = min(g, mi[i])
print(ans)

n, x = map(int, input().split())
a = list(map(int, input().split()))
fst, last, sm = [], [], []
for i in range(1000005):
    fst.append(0)
    last.append(0)
    sm.append(0)
for i in range(n):
    if fst[a[i]] == 0:
        fst[a[i]] = i + 1
    last[a[i]] = i + 1
for i in range(x + 2):
    if fst[i] == 0:
        fst[i] = n + 1
l, ans = 0, 0
for i in range(1, x + 1):
    if fst[i] > l:
        l = max(l, last[i])
        sm[l] += 1
    else:
        break
for i in range(1, n + 1):
    sm[i] += sm[i - 1]
l, i = n + 1, x + 1
while i > 1:
    if last[i] < l:
        l = min(fst[i], l)
        ans += min(sm[l - 1] + 1, i - 1)
    else:
        break
    i -= 1
print(ans)

N, X = map(int, input().split(' '))


class Next():
	def __init__(self, arr):
		# array of length X
		next_ = [None for _ in arr]
		for i in range(len(arr)-2, -1, -1):
			next_[i] = next_[i+1]

			if arr[i+1] != None:
				next_[i] = i+1 
		self.next_ = next_

			

	def get_next(self, value):
		return self.next_[value]

def fast_solution():
	pref = 0
	most_right = last[0]
	if most_right is None:
		most_right = -1

	# Find longest non-decreasing prefix
	while True:
		if pref == X - 1:
			break
		if first[pref+1] is not None and first[pref+1] < most_right:
			break
		pref += 1
		if pref + 1 < X and last[pref] is not None:
			most_right = max(most_right, last[pref])

	# Find longest non-decreasing suffix
	suf = X - 1
	most_left = first[X-1]
	if most_left is None:
		most_left = N
	while True:
		if suf == 0:
			break
		if last[suf-1] is not None and last[suf-1] > most_left:
			break
		suf -= 1
		if suf > 0 and first[suf] is not None:
			most_left = min(most_left, first[suf])

	count = 0
	j = max(suf-1, 0)
	for i in range(min(pref+2, X)):
		j = max(i, j)
		while i>0 and j<X-1 and last[i-1] is not None and next_first.get_next(j) is not None  and last[i-1] > first[next_first.get_next(j)]:
			j += 1
		count += X - j
	return count

def transform(x):
	return int(x) - 1

A = list(map(transform, input().split(' ')))
first = [None for _ in range(X)]
last = [None for _ in range(X)]

for i in range(N):
	x = A[i]
	if first[x] is None:
		first[x] = i

	last[x] = i

next_first = Next(first)

print(fast_solution())

import os
from io import BytesIO, StringIO
#input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

def input_as_list():
    return list(map(int, input().split()))

def array_of(f, *dim):
    return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()

def main():
    n, x = input_as_list()
    a = input_as_list()

    fo = array_of(lambda:-1, x+1)
    lo = array_of(lambda:-1, x+1)

    ans = 0

    for i, e in enumerate(a):
        if fo[e] == -1:
            fo[e] = i
        lo[e] = i

    lastidx = -1
    for i in range(1, x+1):
        if fo[i] != -1:
            if lastidx < fo[i]:
                lastidx = lo[i]
            else:
                i -= 1
                break
    L = i


    firstidx = n+1
    for i in range(x, 0, -1):
        if fo[i] != -1:
            if lo[i] < firstidx:
                firstidx = fo[i]
            else:
                i += 1
                break
    R = i

    ans += min(x - R + 2, x)

    c = n
    for i in range(x, R-1, -1):
        if fo[i] == -1:
            fo[i] = c
        else:
            c = fo[i]

    r = R
    l = 1

    while l <= L:
        if l + 1 < r and (lo[l] == -1 or x < r or lo[l] < fo[r]):
            ans += x - r + 2
            #print(l+1, r-1)
            l += 1
        else:
            r += 1
    #print(L, R, ans)
    print(ans)

main()