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

Source: codeforces | Difficulty: HARD
Tags: Spanning trees

Sorting

Data structures

Divide and conquer


Solutions:
import sys, math, queue, bisect
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)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def add(i, val):
	while i <= n:
		bit[i].append(val)
		i += i & -i

def query(i, x):
	s = 0
	while i > 0:
		pos = bisect.bisect_left(bit[i], x)
		s += len(bit[i]) - pos
		i -= i & -i
	return s
from collections import Counter
import math
bit = []
import bisect
from string import ascii_lowercase as al

def find_max():
	left = []
	st = []
	for i in range(n):
		if not st:
			left.append(-1)
			st.append(i)
		elif st and arr[i] < arr[st[-1]]:
			left.append(st[-1])
			st.append(i)
		else:
			while st and arr[st[-1]] <= arr[i]:
				st.pop()
			if not st:
				st.append(i)
				left.append(-1)
			else:
				left.append(st[-1])
				st.append(i)
	right = []
	st = []
	for i in range(n - 1, -1, -1):
		if not st:
			st.append(i)
			right.append(n)
		elif arr[i] < arr[st[-1]]:
			right.append(st[-1])
			st.append(i)
		else:
			while st and arr[st[-1]] < arr[i]:
				st.pop()
			if st:
				right.append(st[-1])
				st.append(i)
			else:
				right.append(n)
				st.append(i)
	ans = 0
	right = right[::-1]
	for i in range(n):
		x = (right[i] - i) * (i - left[i]) * arr[i]
		if x == 0:
			ans += arr[i]
		else:
			ans += x
	return ans

def find_min():
	left = []
	st = []
	for i in range(n):
		if not st:
			left.append(-1)
			st.append(i)
		elif st and arr[i] > arr[st[-1]]:
			left.append(st[-1])
			st.append(i)
		else:
			while st and arr[st[-1]] >= arr[i]:
				st.pop()
			if not st:
				st.append(i)
				left.append(-1)
			else:
				left.append(st[-1])
				st.append(i)
	right = []
	st = []
	for i in range(n - 1, -1, -1):
		if not st:
			st.append(i)
			right.append(n)
		elif arr[i] > arr[st[-1]]:
			right.append(st[-1])
			st.append(i)
		else:
			while st and arr[st[-1]] > arr[i]:
				st.pop()
			if st:
				right.append(st[-1])
				st.append(i)
			else:
				right.append(n)
				st.append(i)
	ans = 0
	right = right[::-1]
	for i in range(n):
		x = (right[i] - i) * (i - left[i]) * arr[i]
		if x == 0:
			ans += arr[i]
		else:
			ans += x
	return ans
n = int(input())
arr = list(map(int, input().split()))
print(find_max() - find_min())


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


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


import atexit, io, sys, collections, math, heapq, fractions, copy, os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
ais = list(map(int, input().split()))

def check(a, b, flag, mark):
	return (a >= b if mark else a > b) if flag else a <= b if mark else a < b

def build(nums, iter, flag, mark, dv):
	(h, stack) = ([dv for i in range(len(nums))], collections.deque([]))
	for i in iter:
		while stack and check(nums[stack[-1]], nums[i], flag, mark):
			h[stack.pop()] = i
		stack.append(i)
	return h

def f(ais, n):
	ans = 0
	left = [None, None]
	right = [None, None]
	for b in [False, True]:
		(left[int(b)], right[int(b)]) = (build(ais, range(len(ais) - 1, -1, -1), b, False, -1), build(ais, range(len(ais)), b, True, n))
	for i in range(len(ais)):
		q = (i - left[0][i]) * (right[0][i] - i) * ais[i]
		ans += q
		q = (i - left[1][i]) * (right[1][i] - i) * ais[i]
		ans -= q
	return ans
print(f(ais, n))


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


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
stk = [(float('-inf'), int(-1))]
stk1 = [(float('inf'), int(-1))]
leftSmaller = []
leftGreater = []
for (i, a) in enumerate(A):
	while stk[-1][0] > a:
		stk.pop()
	leftSmaller.append(stk[-1][1])
	stk.append((a, i))
	while stk1[-1][0] <= a:
		stk1.pop()
	leftGreater.append(stk1[-1][1])
	stk1.append((a, i))
stk = [(float('-inf'), int(N))]
stk1 = [(float('inf'), int(N))]
rightSmaller = []
rightGreater = []
for i in range(N - 1, -1, -1):
	a = A[i]
	while stk[-1][0] >= a:
		stk.pop()
	rightSmaller.append(stk[-1][1])
	stk.append((a, i))
	while stk1[-1][0] < a:
		stk1.pop()
	rightGreater.append(stk1[-1][1])
	stk1.append((a, i))
rightGreater.reverse()
rightSmaller.reverse()
ans = 0
for (i, a) in enumerate(A):
	ans += a * ((rightGreater[i] - i) * (i - leftGreater[i]) - (rightSmaller[i] - i) * (i - leftSmaller[i]))
print(ans)


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)


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))
	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))
r = 0
for i in range(n):
	r += a[i] * ((i - Ml[i]) * (Mr[i] - i) - (i - ml[i]) * (mr[i] - i))
print(r)


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
	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]
		if x == 0:
			c += a[i]
		else:
			c += x
	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
	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]
		if x == 0:
			c += a[i]
		else:
			c += x
	return c
n = int(input())
arr = [int(x) for x in input().split()]
print(solve1(arr, n) - solve2(arr, n))


import sys
from operator import lt, le, gt, ge
n = int(sys.stdin.buffer.readline().decode('utf-8'))
a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
min_rng = [[0, 0] for _ in range(n)]
max_rng = [[0, 0] for _ in range(n)]
for (j, (st, itr, op1, op2)) in enumerate(((-1, range(n), lt, gt), (n, range(n - 1, -1, -1), le, ge))):
	max_stack = [(st, 10 ** 9)]
	min_stack = [(st, -1)]
	for i in itr:
		while op1(max_stack[-1][1], a[i]):
			max_stack.pop()
		while op2(min_stack[-1][1], a[i]):
			min_stack.pop()
		max_rng[i][j] = max_stack[-1][0]
		min_rng[i][j] = min_stack[-1][0]
		max_stack.append((i, a[i]))
		min_stack.append((i, a[i]))
ans = sum((a[i] * ((max_rng[i][1] - i) * (i - max_rng[i][0]) - (min_rng[i][1] - i) * (i - min_rng[i][0])) for i in range(n)))
print(ans)


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)