Read problems statements in Russian here 

All the chefs (except the Head Chef) are standing in queue to submit their bills. The chefs have different seniority. In all there are N chefs of K different seniority levels. These are given to you in an array, where A_{1}, A_{2}, ..., A_{N} denote the seniority of chefs in the queue. A_{N} denotes front of the queue and A_{1} denotes end of the queue.

Head Chef gets an interesting thought past his head. He begins to think what if every chef starting from the end of the queue begins to delegate his job of submitting bills to a chef least ahead of him in the queue but junior to him. The Head Chef's fearfulness of this scenario is f = i2 - i1 + 1, where i1 is the index of chef in queue and i2 is the index of the junior chef. Head Chef's total fearfulness of chaos is the product of all the fearfulness in Head Chef's mind. Note if a chef has no junior ahead of him/her in the queue then Head Chef's fearfulness for this Chef is 1.

You are required to find the Head Chef's total fearfulness given an arrangement of Chef's in a queue. Since this number can be quite large output it modulo 1000000007. 

------ Input ------ 

Input description.
The first line contains two integers N and  K  denoting the number of chefs and the number of seniority levels. The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the seniority of chefs in the queue. A_{N} denotes front of the queue and A_{1} denotes end of the queue. 

------ Output ------ 

Output description.
Output a single integer denoting the total fearfulness of the Head Chef. 

------ Constraints ------ 

1 ≤ N ≤ 1000000
1 ≤ a_{i} ≤ 1000000
2 ≤ K ≤ 100000

------ Scoring ------ 

Subtask 1 : N ≤ 5000 ( 10 points) 
Subtask 2 : K = 2 ( 10 points)  
Subtask 3 : K ≤ 10 ( 20 points )  
Subtask 4 : See Constraints ( 60 points )  

----- Sample Input 1 ------ 
4 2
1 2 1 2
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
Example case 1. Only the second chef has a junior in front of him and the fearfulness he causes to the head chef is 3 - 2 + 1 = 2. Every other chef causes a fearfulness of 1 for the Head Chef.

Difficulty: HARD
Tags: Data structures

Range queries

Segment trees revisited
Skill types: Data structures

Range queries

Starter code:

Solutions:
(N, K) = list(map(int, input().split()))
arr = list(map(int, input().split()))
a = 1
p = [[arr[-1], 1]]
k = 1
for i in range(N - 2, -1, -1):
	k += 1
	while p[-1][0] >= arr[i]:
		p.pop()
		if p == []:
			break
	if p != []:
		a *= k - p[-1][1] + 1
		a %= 10 ** 9 + 7
	p.append([arr[i], k])
print(a % (10 ** 9 + 7))


(n0, k) = list(map(int, input().split()))
ar = list(map(int, input().split()))
x = 1
y = [[ar[-1], 1]]
j = 1
for i in range(n0 - 2, -1, -1):
	j += 1
	while y[-1][0] >= ar[i]:
		y.pop()
		if y == []:
			break
	if y != []:
		x *= j - y[-1][1] + 1
		x %= 10 ** 9 + 7
	y.append([ar[i], j])
print(x % (10 ** 9 + 7))


(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
x = 1
s = [[arr[-1], 1]]
j = 1
for i in range(n - 2, -1, -1):
	j += 1
	while s[-1][0] >= arr[i]:
		s.pop()
		if s == []:
			break
	if s != []:
		x *= j - s[-1][1] + 1
		x %= 10 ** 9 + 7
	s.append([arr[i], j])
print(x % (10 ** 9 + 7))


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
stk = []
f = 1
for i in range(n):
	while len(stk) != 0 and l[i] < l[stk[-1]]:
		f = f * (i - stk.pop() + 1) % 1000000007
	stk.append(i)
print(f)


(n, k) = map(int, input().split())
l = [int(x) for x in input().split()]
t = []
f = 1
m = 1000000007
for i in range(n):
	while len(t) != 0 and l[i] < l[t[-1]]:
		f = f * (i - t.pop() + 1) % m
	t.append(i)
print(f)


if 3 > 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	stk = []
	ans = 1
	for i in range(n):
		while len(stk) > 0 and l[i] < l[stk[-1]]:
			e = stk.pop()
			ans = ans * (i - e + 1) % 1000000007
		stk.append(i)
	print(ans)


(n, k) = map(int, input().split())
a = [int(i) for i in input().split()][:n]
st = []
ans = 1
for i in range(n):
	while len(st) > 0 and a[i] < a[st[-1]]:
		ele = st.pop()
		ans = ans * (i - ele + 1) % 1000000007
	st.append(i)
print(ans)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
m = 1000000007
s = []
total = 1
i = n - 1
while i >= 0:
	e = arr[i]
	while s and arr[s[-1]] >= e:
		s.pop()
	if s:
		total = total % m * (s[-1] - i + 1) % m % m
	s.append(i)
	i -= 1
print(total)


for _ in range(1):
	(n, k) = map(int, input().split())
	queue = list(map(int, input().split()))
	ans = 1
	stack = []
	i = n - 1
	m = 10 ** 9 + 7
	while i >= 0:
		temp = queue[i]
		while stack and temp <= queue[stack[-1]]:
			stack.pop(-1)
		if stack:
			ans = ans % m * (stack[-1] - i + 1) % m % m
		stack.append(i)
		i -= 1
	print(ans)


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
index = []
i = n - 1
ans = 1
m = 10 ** 9 + 7
while i >= 0:
	while index and l[index[-1]] >= l[i]:
		index.pop(-1)
	if index:
		ans = ans % m * (index[-1] - i + 1) % m
	index.append(i)
	i -= 1
print(ans % m)


(N, K) = (int(x) for x in input().split())
l = [int(x) for x in input().split()]
f = 1
stack = []
for i in range(N):
	while stack and l[i] < l[stack[-1]]:
		f = f * (i - stack.pop() + 1) % 1000000007
	stack.append(i)
print(f)


try:
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()][:n]
	st = [(float('-inf'), len(l))]
	prod = 1
	ans = 1
	for i in range(n):
		while l[i] < st[-1][0]:
			prod = i - st[-1][1] + 1
			ans = ans * prod % 1000000007
			st.pop()
		st.append((l[i], i))
	print(ans)
except:
	pass


(N, K) = map(int, input().split())
arr = list(map(int, input().split()))
stack = []
output = 1
for i in range(N):
	while len(stack) != 0 and arr[i] < arr[stack[-1]]:
		element = stack.pop()
		output = output * (i - element + 1) % 1000000007
	stack.append(i)
print(output)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
mod = 1000000007
res = 1
stack = []
for i in range(len(arr)):
	while len(stack) != 0 and arr[stack[-1]] > arr[i]:
		res = res * (i - stack.pop() + 1) % mod
	stack.append(i)
print(res)


(a, b) = (int(a) for a in input().split())
l = [int(a) for a in input().split()]
d = 1
stack = []
for i in range(a):
	while stack and l[i] < l[stack[-1]]:
		d = d * (i - stack.pop() + 1) % 1000000007
	stack.append(i)
print(d)


(n, k) = map(int, input().split())
lst = list(map(int, input().strip().split()))[:n]
fear = 1
mod = 1000000007
s = []
for i in range(0, n):
	while len(s) != 0 and lst[i] < lst[s[-1]]:
		fear = fear * (i - s.pop() + 1) % mod
	s.append(i)
print(fear)


(n, k) = map(int, input().split())
lst = list(map(int, input().split()))
st = []
temp = 1
for i in range(n):
	while len(st) != 0 and lst[i] < lst[st[-1]]:
		temp = temp * (i - st.pop() + 1) % 1000000007
	st.append(i)
print(temp)


def check(x, y):
	d = 1000000007
	return x * y % d
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
arr = []
ans = 1
for i in range(n):
	while arr and a[arr[-1]] > a[i]:
		ans = check(ans, i - arr.pop() + 1)
	arr.append(i)
print(ans)


(t, m) = map(int, input().split())
l = list(map(int, input().split()))
stk = []
m = 1
for i in range(t):
	while len(stk) != 0 and l[i] < l[stk[-1]]:
		m = m * (i - stk.pop() + 1) % 1000000007
	stk.append(i)
print(m)


def chefs(l, n):
	stack1 = []
	stack2 = []
	sum1 = 1
	x = 1
	y = 1000000007
	for i in range(n - 1, -1, -1):
		while len(stack1) != 0 and stack1[-1] >= l[i]:
			stack1.pop()
			stack2.pop()
		if len(stack1) == 0:
			sum1 = 1
		else:
			sum1 = stack2[-1] - i + 1
		stack1.append(l[i])
		stack2.append(i)
		x = x * sum1 % y
	return x
(n, k) = map(int, input().split())
l = list(map(int, input().split()))
print(chefs(l, n))


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
stk = []
tf = 1
for i in range(len(a)):
	while len(stk) and a[stk[-1]] > a[i]:
		tf *= i - stk[-1] + 1
		tf %= 1000000007
		stk.pop()
	stk.append(i)
print(tf)


(X, Y) = (int(x) for x in input().split())
l = [int(x) for x in input().split()]
f = 1
stack = []
for i in range(X):
	while stack and l[i] < l[stack[-1]]:
		f = f * (i - stack.pop() + 1) % 1000000007
	stack.append(i)
print(f)


(n, k) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
n = len(arr)
result = 1
stack = []
for i in range(n):
	while len(stack) and arr[stack[-1]] > arr[i]:
		result *= i - stack[-1] + 1
		result %= 1000000007
		stack.pop()
	stack.append(i)
print(result)


def mul(a, b):
	return a * b % 1000000007
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
s = []
ans = 1
for i in range(n):
	while s and a[s[-1]] > a[i]:
		ans = mul(ans, i - s.pop() + 1)
	s.append(i)
print(ans)


from sys import stdin
input = stdin.readline
mod = 10 ** 9 + 7

def mul(a, b):
	return a % mod * (b % mod) % mod

def answer():
	s = []
	ans = [1] * n
	for i in range(n):
		while len(s) and a[i] < a[s[-1]]:
			ans[s[-1]] = i - s[-1] + 1
			s.pop()
		s.append(i)
	val = 1
	for i in range(n):
		val = mul(val, ans[i])
	return val
for T in range(1):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(answer())


prime = 1000000007
t = 1
for test in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	stack = [(0, -1)]
	prod = 1
	for i in range(len(arr)):
		for j in range(len(stack) - 1, -1, -1):
			if arr[i] >= stack[j][0]:
				stack.append((arr[i], i))
				break
			else:
				prod = prod * (i - stack[j][1] + 1) % prime
				stack.pop()
	print(prod)


(N, K) = (int(x) for x in input().split())
list1 = list((int(x) for x in input().split()))
fear = 1
stack = []
for i in range(N):
	while stack and list1[i] < list1[stack[-1]]:
		fear = fear * (i - stack.pop() + 1) % 1000000007
	stack.append(i)
print(fear)


mod = 1000000007
(n, k) = map(int, input().split())
Q = list(map(int, input().split()))
S = []
fearfulness = 1
for i in range(n):
	while S and Q[i] < Q[S[-1]]:
		fearfulness = fearfulness * (i - S.pop() + 1) % mod
	S.append(i)
print(fearfulness)


(n, k) = map(int, input().split())
l1 = list(map(int, input().split()))
stack = []
ans = 1
for i in range(n):
	while stack and l1[i] < l1[stack[-1]]:
		ans *= i - stack.pop() + 1
		ans %= 1000000007
	stack.append(i)
print(ans)


v = 1000000007
(n, k) = map(int, input().split())
l = list(map(int, input().split()))
s = []
c = 1
for i in range(n):
	while s and l[i] < l[s[-1]]:
		c = c * (i - s.pop() + 1) % v
	s.append(i)
print(c)


val = 1000000007
(n, k) = map(int, input().split())
li = [int(x) for x in input().split()]
s = []
ans = 1
for i in range(n):
	while s and li[i] < li[s[-1]]:
		ans = ans * (i - s.pop() + 1) % val
	s.append(i)
print(ans)


maxi = 1000000007
(n, k) = map(int, input().split())
li = list(map(int, input().split()))
s = []
x = 1
for i in range(n):
	while s and li[i] < li[s[-1]]:
		x = x * (i - s.pop() + 1) % maxi
	s.append(i)
print(x)


(x, y) = map(int, input().split())
a = [int(n) for n in input().split()]
S = []
r = 1
l = 1000000007
for i in range(x):
	while S and a[i] < a[S[-1]]:
		r = r * (i - S.pop() + 1) % l
	S.append(i)
print(r)


m = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
s = []
c = 1
for i in range(n):
	while s and a[i] < a[s[-1]]:
		c = c * (i - s.pop() + 1) % m
	s.append(i)
print(c)


(n, k) = map(int, input().split())
li = [int(x) for x in input().split()]
s = []
res = 1
m = 1000000007
for i in range(n):
	while s and li[i] < li[s[-1]]:
		res = res * (i - s.pop() + 1) % m
	s.append(i)
print(res)


(a, b) = map(int, input().split())
l = [int(x) for x in input().split()]
s = []
res = 1
m = 1000000007
for i in range(a):
	while s and l[i] < l[s[-1]]:
		res = res * (i - s.pop() + 1) % m
	s.append(i)
print(res)


(a, b) = map(int, input().split())
z = list(map(int, input().split()))
m = 1000000007
s = []
k = 1
for i in range(a):
	while len(s) != 0 and z[i] < z[s[-1]]:
		k = k * (i - s.pop(-1) + 1) % m
	s.append(i)
print(k)


(n, k) = map(int, input().split())
li = [int(x) for x in input().split()]
stk = list()
ans = [1] * n
stk.append(0)
for i in range(1, n):
	while stk:
		if li[i] < li[stk[-1]]:
			ind = stk[-1]
			f = i - stk[-1] + 1
			ans[ind] = f
			stk.pop()
		else:
			break
	stk.append(i)
res = 1
for i in ans:
	res = res % 1000000007 * (i % 1000000007) % 1000000007
print(res)


(n, m) = map(int, input().split())
p = []
top = -1
f = 1
li = map(int, input().split())
for (i, m) in enumerate(li):
	if top == -1:
		p.append((i + 1, m))
		top += 1
	else:
		while top != -1 and p[top][1] > m:
			t = p.pop()
			f *= i + 1 - t[0] + 1
			f %= 1000000007
			top -= 1
		p.append((i + 1, m))
		top += 1
print(f)


(x, y) = map(int, input().split())
l = list(map(int, input().split()))
m = 1000000007
s = []
p = 1
for i in range(x):
	while len(s) != 0 and l[i] < l[s[-1]]:
		p = p * (i - s.pop(-1) + 1) % m
	s.append(i)
print(p)


(a, b) = map(int, input().split())
ls = list(map(int, input().split()))
m = 1000000007
stk = []
k = 1
for i in range(a):
	while len(stk) != 0 and ls[i] < ls[stk[-1]]:
		k = k * (i - stk.pop(-1) + 1) % m
	stk.append(i)
print(k)


p = 1000000007

def mul(a, b):
	return a * b % p
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
st = []
k = 1
for i in range(n):
	while st and a[st[-1]] > a[i]:
		k = mul(k, i - st.pop() + 1)
	st.append(i)
print(k)