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)$.

Source: codeforces | Difficulty: HARD
Tags: Data structures

Combinatorics

Amortized analysis

Sorting


Solutions:
(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)


import os
from io import BytesIO, StringIO

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
			l += 1
		else:
			r += 1
	print(ans)
main()


import sys
input = sys.stdin.readline
(n, x) = 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(ANS)


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

class Next:

	def __init__(self, arr):
		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
	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])
	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 sys
input = sys.stdin.readline
from bisect import bisect_left as bl
(n, x) = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

def naive(a, x):
	res = 0
	for l in range(x):
		for r in range(l, x):
			L = list(filter(lambda x: not l <= x <= r, a))
			res += L == sorted(L)
	return res
if all((a[i] >= a[i - 1] for i in range(1, len(a)))):
	res = x * (x + 1) // 2
else:
	(mn, mx) = ([n + 1 for _ in range(x)], [-1 for _ in range(x)])
	for (i, e) in enumerate(a):
		mn[e] = min(mn[e], i)
		mx[e] = max(mx[e], i)
	mnc = [mn[x - 1]]
	for i in range(x - 2, -1, -1):
		mnc.append(min(mnc[-1], mn[i]))
	mnc = mnc[::-1]
	left = 0
	M = mx[0]
	while left < x - 1:
		if mn[left + 1] > M:
			M = max(M, mx[left + 1])
			left += 1
		else:
			break
	right = x - 1
	M = mn[x - 1]
	while right > 0:
		if mx[right - 1] < M:
			M = min(M, mn[right - 1])
			right -= 1
		else:
			break
	res = 1 + x - right + left + 1
	M = mx[0]
	for i in range(left + 1):
		ind = max(bl(mnc, M), right)
		res += x - ind
		M = max(M, mx[i + 1])
print(res)


(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)