Coolguy gives you a simple problem. Given a $1$-indexed array, $\mbox{A}$, containing $N$ elements, what will $\textit{and}$ be after this pseudocode is implemented and executed? Print $and\%(10^9+7)$.

//f(a, b) is a function that returns the minimum element in interval [a, b]

ans = 0

for a -> [1, n]
    for b -> [a, n]
        for c -> [b + 1, n]
            for d -> [c, n]
                ans = ans + min(f(a, b), f(c, d))

Input Format

The first line contains $N$ (the size of array $\mbox{A}$). 

The second line contains $N$ space-separated integers describing $\mbox{A}$.

Constraints

$1$ ≤ $N$ ≤ $2\times10^5$
$1$ ≤ $A_i$ ≤ $\mathbf{10^{9}}$

Note: $\mbox{A}$ is $1$-indexed (i.e.: $A=\{A_1,A_2,\text{...},A_{N-1},A_N\}$).

Output Format

Print the integer result of $and\%(10^9+7)$.

Sample Input
3
3 2 1

Sample Output
6

Explanation

$min(~f(1,1),~f(2,2)~)=2$

$min(~f(1,1),~f(2,3)~)=1$

$min(~f(1,1),~f(3,3)~)=1$

$min(~f(1,2),~f(3,3)~)=1$

$min(~f(2,2),~f(3,3)~)=1$ 

We then sum these numbers ($2+1+1+1+1=6$) and print $6\%(10^9+7)$, which is $\boldsymbol{6}$.

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import os
import sys

def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


import sys
N = int(sys.stdin.readline())
A = map(int, sys.stdin.readline().split())
M = 10 ** 9 + 7

def main():
	ord_to_val = {}
	ord_to_ind = {}
	for (o, (i, v)) in enumerate(sorted(enumerate(A), key=lambda iv: iv[1])):
		ord_to_val[o] = v
		ord_to_ind[o] = i
	segment_inds = [(0, N - 1)]
	total = 0
	all_tri = tri(N)
	for ordv in range(N):
		ind = ord_to_ind[ordv]
		segment_index = find_segment(ind, segment_inds)
		(first, last) = segment_inds[segment_index]
		seg_tri = tri(last - first + 1)
		to_left = ind - first
		to_right = last - ind
		ext_tri = all_tri - seg_tri
		weight = worth(to_left, to_right, ext_tri)
		value = weight * ord_to_val[ordv] % M
		total = (total + value) % M
		update_segment_inds(segment_inds, segment_index, first, last, ind)
		all_tri = (all_tri - seg_tri + tri(to_left) + tri(to_right)) % M
	return total

def find_segment(ind, segment_inds):
	index = bisect_r(segment_inds, ind) - 1
	return index

def bisect_r(vals, val):
	lo = 0
	hi = len(vals)
	while lo < hi:
		mid = (lo + hi) // 2
		if val < vals[mid][0]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def update_segment_inds(segment_inds, segment_index, first, last, ind):
	if ind == first:
		new_segments = [(first + 1, last)]
	elif ind == last:
		new_segments = [(first, last - 1)]
	else:
		new_segments = [(first, ind - 1), (ind + 1, last)]
	segment_inds[segment_index:segment_index + 1] = new_segments

def worth(m, n, ext_tri):
	n_sum = n * (n + 1) * (n + 2) // 6 % M
	m_sum = m * (m + 1) * (m + 2) // 6 % M
	e_sum = ext_tri * (n + 1) * (m + 1) % M
	return ((n + 1) * m_sum + (m + 1) * n_sum + e_sum) % M

def tri(x):
	return x * (x + 1) // 2 % M
print(main())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


def smart():
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	singles = pairs = 0
	ans = 0

	def remove(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		singles -= s
		pairs -= (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles

	def add(k):
		nonlocal singles, pairs
		s = k * (k + 1) // 2
		pairs += (k + 2) * (k + 1) * k * (k - 1) // 24 + s * singles
		singles += s
	for i in sorted(range(1, n + 1), key=A.__getitem__)[::-1]:
		(l, r) = (left[i - 1], right[i + 1])
		k = l + 1 + r
		right[i - l] = left[i + r] = k
		oldpairs = pairs
		remove(l)
		remove(r)
		add(k)
		ans += A[i] * (pairs - oldpairs)
	return ans % (10 ** 9 + 7)
n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())