You are given an array a consisting of n elements. The imbalance value of some subsegment of this array is the difference between the maximum and minimum element from this segment. The imbalance value of the array is the sum of imbalance values of all subsegments of this array.

For example, the imbalance value of array [1, 4, 1] is 9, because there are 6 different subsegments of this array:   [1] (from index 1 to index 1), imbalance value is 0;  [1, 4] (from index 1 to index 2), imbalance value is 3;  [1, 4, 1] (from index 1 to index 3), imbalance value is 3;  [4] (from index 2 to index 2), imbalance value is 0;  [4, 1] (from index 2 to index 3), imbalance value is 3;  [1] (from index 3 to index 3), imbalance value is 0; 

You have to determine the imbalance value of the array a.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 10^6) — size of the array a.

The second line contains n integers a_1, a_2... a_{n} (1 ≤ a_{i} ≤ 10^6) — elements of the array.


-----Output-----

Print one integer — the imbalance value of a.


-----Example-----
Input
3
1 4 1

Output
9

Difficulty: interview

Starter code:

Solutions:

#taken from https://stackoverflow.com/questions/30698441/optimal-way-to-find-sums-of-all-contiguous-sub-arrays-max-difference
def max_sums(d):
    stack = [(-1, float('inf'))]
    sum_ = 0
    for i, x in enumerate(d):
        while x > stack[-1][1]:
            prev_i, prev_x = stack.pop()
            prev_prev_i, prev_prev_x = stack[-1]
            sum_ += prev_x * (i - prev_i) * (prev_i - prev_prev_i)
        stack.append((i, x))
    while len(stack) > 1:
        prev_i, prev_x = stack.pop()
        prev_prev_i, prev_prev_x = stack[-1]
        sum_ += prev_x * (len(d) - prev_i) * (prev_i - prev_prev_i)
    return sum_

def max_differences_sum(d):
    return max_sums(d) + max_sums([-x for x in d])

n=int(input())
l=list(map(int,input().split()))
print(max_differences_sum(l))

n = int(input())
a = list(map(int,input().split()))
left = [None for _ in range(n)]
right = [None for _ in range(n)]
left1 = [None for _ in range(n)]
right1 = [None for _ in range(n)]
class Stack(object):
    def __init__(self):
        self.c = []
    def push(self,new):
        self.c.append(new)
    def pop(self):
        return self.c.pop(-1)
    def vide(self):
        return self.c == []
    def peek(self):
        return self.c[-1]
def calculleft():
    s = Stack()
    for i in range(n):
        while not s.vide() and a[s.peek()] > a[i]:
            s.pop()
        if not s.vide():
            left[i] = s.peek()
        else:
            left[i] = -1
        s.push(i)

def calculright():
    s = Stack()
    for i in range(n-1,-1,-1):
        while not s.vide() and a[s.peek()] >= a[i]:
            s.pop()
        if not s.vide():
            right[i] = s.peek()
        else:
            right[i] = n
        s.push(i)
        
def calculleft1():
    s = Stack()
    for i in range(n):
        while not s.vide() and a[s.peek()] < a[i]:
            s.pop()
        if not s.vide():
            left1[i] = s.peek()
        else:
            left1[i] = -1
        s.push(i)

def calculright1():
    s = Stack()
    for i in range(n-1,-1,-1):
        while not s.vide() and a[s.peek()] <= a[i]:
            s.pop()
        if not s.vide():
            right1[i] = s.peek()
        else:
            right1[i] = n
        s.push(i)
     
res = 0
calculleft()
calculright()
calculleft1()
calculright1()

res2 = 0
for i in range(n):
    res += (i-left[i])*(right[i]-i)*a[i]
    res2 += (i-left1[i])*(right1[i]-i)*a[i]
print(res2-res)
    


n = int(input())
a = list(map(int, input().split()))
left = [-1 for i in range(n)]
right = [n for i in range(n)]
stack = []
for i in range(n):
    while stack and a[stack[-1]] > a[i]:
        stack.pop()
    if stack:
        left[i] = stack[-1]
    stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
    while stack and a[stack[-1]] >= a[i]:
        stack.pop()
    if stack:
        right[i] = stack[-1]
    stack.append(i)
res = 0
for i in range(n):
    res -= a[i] * (i - left[i]) * (right[i] - i)
left = [-1 for i in range(n)]
right = [n for i in range(n)]
stack = []
for i in range(n):
    while stack and a[stack[-1]] < a[i]:
        stack.pop()
    if stack:
        left[i] = stack[-1]
    stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
    while stack and a[stack[-1]] <= a[i]:
        stack.pop()
    if stack:
        right[i] = stack[-1]
    stack.append(i)
for i in range(n):
    res += a[i] * (i - left[i]) * (right[i] - i)
print(res)

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

def findMinimumL(a):
    A = [-1]*len(a)
    for i,x in enumerate(a):
        j = i - 1 
        while j != -1 and a[j] > a[i]:
            j = A[j]
        A[i] = j
    return A

def findMaximumL(a):
    A = [-1]*len(a)
    for i,x in enumerate(a):
        j = i - 1 
        while j != -1 and a[j] < a[i]:
            j = A[j]
        A[i] = j
    return A

def findMinimumR(a):
    A = [-1]*len(a)
    for i in range(len(a) - 1,-1,-1):
        j = i + 1
        while j != len(a) and a[j] >= a[i]:
            j = A[j]
        A[i] = j
    return A

def findMaximumR(a):
    A = [-1]*len(a)
    for i in range(len(a) - 1,-1,-1):
        j = i + 1
        while j != len(a) and a[j] <= a[i]:
            j = A[j]
        A[i] = j
    return A

def minimumSum():
    L,R = findMinimumL(a), findMinimumR(a)
    ans = 0
    for i,x in enumerate(a):
        ans += (i - L[i])*(R[i] - i)*x
    return ans

def maximumSums():
    L,R = findMaximumL(a), findMaximumR(a)
    ans = 0
    for i,x in enumerate(a):
        ans += (i - L[i])*(R[i] - i)*x
    return ans

print(maximumSums() - minimumSum())



import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def gt(a,b):
	return a>b

def gte(a,b):
	return a>=b

def lt(a,b):
	return a<b

def lte(a,b):
	return a<=b

def d(a,cmp,val):
	n = len(a)
	st = [(val,-1)]
	r = [0]*n
	for i in range(len(a)):
		v = a[i]
		while cmp(v,st[-1][0]):
			st.pop()
		r[i] = st[-1][1]
		st.append((v,i))
		#print(st)
	return r
def rr(a):
	n = len(a)
	r = [0]*n
	for i in range(n):
		r[n-i-1] = n-a[i]-1
	return r
n = mint()
a = list(mints())
b = a[::-1]
Ml = d(a,gt,(10**9))
Mr = rr(d(b,gte,(10**9)))
ml = d(a,lt,-(10**9))
mr = rr(d(b,lte,-(10**9)))
#print(a)
#print(Ml)
#print(Mr)
#print(b)
#print(ml)
#print(mr)
r = 0
for i in range(n):
	r += a[i]*((i-Ml[i])*(Mr[i]-i)-(i-ml[i])*(mr[i]-i))
print(r)

import sys

def pro():
	return sys.stdin.readline().strip()

def rop():
	return map(int, pro().split())

def a_b_b(a, b):
	return a > b

def a_br_b(a, b):
	return a >= b

def a_m_b(a, b):
	return a < b

def a_mr_b(a, b):
	return a <= b

def ry(a, c, t):
	q = len(a)
	x = [(t, -1)]
	r = [0] * q
	
	for i in range(len(a)):
		v = a[i]
		
		while c(v, x[-1][0]):
			x.pop()
		r[i] = x[-1][1]
		x.append((v, i))
		
	return r

def tyr(a):
	q = len(a)
	r = [0] * q
	
	for i in range(q):
		r[q - i - 1] = q - a[i] - 1
		
	return r

def main():
	s = int(pro())
	a = list(rop())
	z = a[::-1]
	o = 10 ** 9
	r = 0
	
	m = ry(a, a_b_b, o)
	n = tyr(ry(z, a_br_b, o))
	b = ry(a, a_m_b, -o)
	v = tyr(ry(z, a_mr_b, -o))
	
	for i in range(s):
		r += a[i] * ((i - m[i]) * (n[i] - i) - (i - b[i]) * (v[i] - i))
		
	print(r)
main()

#Bhargey Mehta (Sophomore)
#DA-IICT, Gandhinagar
import sys, math, queue, bisect
#sys.stdin = open("input.txt", "r")
MOD = 10**9+7
sys.setrecursionlimit(1000000)

def mxr(x):
    n = len(x)
    ans = [n for i in range(n)]
    s = []
    for i in range(n):
        while len(s) > 0 and x[s[-1]] < x[i]:
            ans[s.pop()] = i
        s.append(i)
    return ans

def mnr(x):
    n = len(x)
    ans = [n for i in range(n)]
    s = []
    for i in range(n):
        while len(s) > 0 and x[s[-1]] > x[i]:
            ans[s.pop()] = i
        s.append(i)
    return ans

def mxl(x):
    ans = [-1 for i in range(n)]
    s = []
    for i in range(n-1, -1, -1):
        while len(s) > 0 and x[s[-1]] <= x[i]:
            ans[s.pop()] = i
        s.append(i)
    return ans

def mnl(x):
    ans = [-1 for i in range(n)]
    s = []
    for i in range(n-1, -1, -1):
        while len(s) > 0 and x[s[-1]] >= x[i]:
            ans[s.pop()] = i
        s.append(i)
    return ans

n = int(input())
a = list(map(int, input().split()))
maxl = mxl(a)
minl = mnl(a)
maxr = mxr(a)
minr = mnr(a)
ans = 0
for i in range(n):
    mxrng = (maxr[i]-i)*(i-maxl[i])
    mnrng = (minr[i]-i)*(i-minl[i])
    ans += a[i]*(mxrng-mnrng)
print(ans)

def solve1(a, n):  
    left=[]
    st=[]
    i=0
    while i<(n):
        if not st:
            left.append(-1)
            st.append(i)
            
        elif st and a[i]<a[st[-1]]:
            left.append(st[-1])
            st.append(i)
        else:
            while st and a[i]>a[st[-1]]:
                st.pop()
                
            if not st:
                st.append(i)
                left.append(-1)
                
            else:
                left.append(st[-1])
                st.append(i)
                
                
        i+=1
    # print(left)
    right=[]
    st=[]
    i=n-1
    while i>(-1):
        if not st:
            right.append(n)
            st.append(i)
            
        elif st and a[i]<a[st[-1]]:
            right.append(st[-1])
            st.append(i)
        else:
            while st and a[i]>=a[st[-1]]:
                st.pop()
                
            if not st:
                st.append(i)
                right.append(n)
                
            else:
                right.append(st[-1])
                st.append(i)
                
                
        i-=1
    right=right[::-1]
    c=0
    for i in range(len(left)):
        x=(right[i]-i)*(i-left[i])*a[i]
        # print(x)
        if x==0:
            c+=a[i]
        else:
            c+=x
    # print(c)
    # print(a)
    # print(left)
    # print(right)
            
    return c

    

            
def solve2(a, n): 
    left=[]
    st=[]
    i=0
    while i<(n):
        if not st:
            left.append(-1)
            st.append(i)
            
        elif st and a[i]>a[st[-1]]:
            left.append(st[-1])
            st.append(i)
        else:
            while st and a[i]<a[st[-1]]:
                st.pop()
                
            if not st:
                st.append(i)
                left.append(-1)
                
            else:
                left.append(st[-1])
                st.append(i)
                
                
        i+=1
    # print(left)
    right=[]
    st=[]
    i=n-1
    while i>(-1):
        if not st:
            right.append(n)
            st.append(i)
            
        elif st and a[i]>a[st[-1]]:
            right.append(st[-1])
            st.append(i)
        else:
            while st and a[i]<=a[st[-1]]:
                st.pop()
                
            if not st:
                st.append(i)
                right.append(n)
                
            else:
                right.append(st[-1])
                st.append(i)
                
                
        i-=1
    right=right[::-1]
    # print(right)
    c=0
    for i in range(len(left)):
        x=(right[i]-i)*(i-left[i])*a[i]
        # print(x)
        if x==0:
            c+=a[i]
        else:
            c+=x
    # print(c)
    # print(a)
    # print(left)
    # print(right)
            
    return c



n=int(input())
arr=[int(x) for x in input().split()]
# solve2(arr,n)
# print(solve1(arr,n))
# print(solve2(arr,n))
# print()
# (solve2(arr,n))

print(solve1(arr,n)-solve2(arr,n))