Doctor Kunj installed new software on cyborg Shresth.
This software introduced Shresth to range minimum queries.
Cyborg Shresth thought of T$T$ different problems in each of which you will be given
an array A$A$ of length N$N$ and an array B$B$ of length M$M$. In each of these problems, you have to calculate:
∑mi=1∑mj=irangeMin(B[i],B[j])$\sum_{i=1}^m \sum_{j=i}^m rangeMin(B[i],B[j])$
Where rangeMin(i,j)$rangeMin(i,j)$ returns the minimum element in the range of indices i$i$ to j$j$ (both included) in array A$A$.
It is given that array B$B$ consists of pairwise distinct elements and is in ascending order.

-----Input Format:-----
- First line will contain T$T$, the number of different problems Cyborg Shresth thought of.
- Each problem's input data will be given in three different lines. 
- The first line will contain N$N$ and M$M$, the length of array A$A$ and B$B$ respectively. 
- The second line will contain N$N$ space separated positive integers, which form the array A$A$. - 
- The third line will contain M$M$ space separated positive integers, which form the array B$B$.

-----Output Format:-----
- For each different problem, print on a new line the answer to the problem, i.e. the value of ∑mi=1∑mj=irangeMin(B[i],B[j])$\sum_{i=1}^m \sum_{j=i}^m rangeMin(B[i],B[j])$ .

-----Constraints:-----
- 1≤T≤105$1 \leq T \leq {10}^5$
- 1≤N≤105$1 \leq N \leq {10}^5$
- 1≤M≤105$1 \leq M \leq {10}^5$
- 1≤A[i]≤109$1 \leq A[i] \leq 10^9$
- 1≤B[i]≤N$1 \leq B[i] \leq N$
It is guaranteed that the sum of N$N$ over all test cases does not exceed 106${10}^6$ .

-----Sample Input:-----
1
7 3
10 3 7 9 1 19 2
1 4 6

-----Sample Output:-----
43

-----Explanation:-----
For the given array A$A$, we have to calculate rangeMin(1,1)+rangeMin(1,4)+rangeMin(1,6)+rangeMin(4,4)+rangeMin(4,6)+rangeMin(6,6)$rangeMin(1,1) + rangeMin(1,4) + rangeMin(1,6) + rangeMin(4,4) + rangeMin(4,6) + rangeMin(6,6) $.
This is equal to 10+3+1+9+1+19=43$10 + 3 + 1 + 9 + 1 +19 = 43$.

Difficulty: VERY_HARD

Starter code:

Solutions:
def f(a, n):
	(l, r, s1, s2) = ([0] * n, [0] * n, [], [])
	for i in range(n):
		count = 1
		while len(s1) > 0 and a[i] < s1[-1][0]:
			count += s1[-1][1]
			s1.pop()
		s1.append((a[i], count))
		l[i] = count
	for i in range(n - 1, -1, -1):
		count = 1
		while len(s2) > 0 and a[i] <= s2[-1][0]:
			count += s2[-1][1]
			s2.pop()
		s2.append((a[i], count))
		r[i] = count
	count = 0
	for i in range(n):
		count += a[i] * l[i] * r[i]
	return count
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	s = 0
	for i in b:
		s += a[i - 1]
	for i in range(m - 1):
		c.append(min(a[b[i] - 1:b[i + 1]]))
	s += f(c, m - 1)
	print(s)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [0] + list(map(int, input().split()))
	c = list(map(int, input().split()))
	b = [0] * (n + 1)
	for x in c:
		b[x] += 1
	for i in range(1, n + 1):
		b[i] += b[i - 1]
	s = [0] * (n + 1)
	i = -1
	r = 0
	for k in range(1, n + 1):
		while i > -1 and a[s[i]] > a[k]:
			if i > 0:
				r += a[s[i]] * (b[s[i]] - b[s[i - 1]]) * (b[k - 1] - b[s[i] - 1])
			else:
				r += a[s[i]] * b[s[i]] * (b[k - 1] - b[s[i] - 1])
			i -= 1
		i += 1
		s[i] = k
	k = n + 1
	while i > -1:
		if i > 0:
			r += a[s[i]] * (b[s[i]] - b[s[i - 1]]) * (b[k - 1] - b[s[i] - 1])
		else:
			r += a[s[i]] * b[s[i]] * (b[k - 1] - b[s[i] - 1])
		i -= 1
	print(r)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = 0
	for i in range(m):
		b[i] -= 1
		s += a[b[i]]
	ms = [min(a[b[i]:b[i + 1] + 1]) for i in range(m - 1)]
	ls = []
	rs = []
	stk = [(-float('inf'), -1)]
	for i in range(len(ms)):
		while stk[-1][0] > ms[i]:
			stk.pop()
		ls.append(i - stk[-1][1])
		stk.append((ms[i], i))
	ms.reverse()
	stk = [(-float('inf'), -1)]
	for i in range(len(ms)):
		while stk[-1][0] >= ms[i]:
			stk.pop()
		rs.append(i - stk[-1][1])
		stk.append((ms[i], i))
	rs.reverse()
	ms.reverse()
	for i in range(len(ms)):
		s += ls[i] * rs[i] * ms[i]
	print(s)


def f(a, n):
	(l, r, s1, s2) = ([0] * n, [0] * n, [], [])
	for i in range(n):
		count = 1
		while len(s1) > 0 and a[i] < s1[-1][0]:
			count += s1[-1][1]
			s1.pop()
		s1.append((a[i], count))
		l[i] = count
	for i in range(n - 1, -1, -1):
		count = 1
		while len(s2) > 0 and a[i] <= s2[-1][0]:
			count += s2[-1][1]
			s2.pop()
		s2.append((a[i], count))
		r[i] = count
	count = 0
	for i in range(n):
		count += a[i] * l[i] * r[i]
	return count
t = int(input())