Chef has a sequence of N integers A_{1}, A_{2},\dots, A_{N}. He defines a function f(i, j) as follows:

f(i, j) = A_{i} + max(A_{i}, A_{i + 1}) + max(A_{i}, A_{i + 1}, A_{i + 2}) + \dots + max(A_{i}, A_{i + 1}, \dots, A_{j})

Chef tries to find the sum of f(i, j) over all (i, j) such that 1 ≤ i ≤ j ≤ N (i.e \sum\limits_{i=1}^n \sum\limits_{j=i}^nf(i, j)), but fails. Can you help him find the sum? 

Since the sum can be very large, find it modulo (10^{9} + 7).

Note: Since the size of the input and output is large, please use fast input-output methods.

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N.
- The second line contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}.

------ Output Format ------ 

For each test case, print a single line containing one integer - the required sum i.e \sum\limits_{i=1}^n \sum\limits_{j=i}^nf(i, j) modulo (10^{9} + 7).

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

$1 ≤ T ≤ 5\cdot 10^{3}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
3
2
1 2
3
1 2 3
4
5 4 1 3

----- Sample Output 1 ------ 
6
20
82

----- explanation 1 ------ 
Test case $1$: 

- $f(1, 1) = A_{1} = 1$.
- $f(1, 2) = A_{1} + max(A_{1}, A_{2}) = 1 + max(1, 2) = 1 + 2 = 3$.
- $f(2, 2) = A_{2} = 2$. 

Hence the required sum $= 1 + 3 + 2 = 6$.

Test case $2$: 

- $f(1, 1) = A_{1} = 1$.
- $f(1, 2) = A_{1} + max(A_{1}, A_{2}) = 1 + max(1, 2) = 1 + 2 = 3$.
- $f(1, 3) = A_{1} + max(A_{1}, A_{2}) + max(A_{1}, A_{2}, A_{3}) = 1 + max(1, 2) + max(1, 2, 3) = 1 + 2 + 3 = 6$.
- $f(2, 2) = A_{2} = 2$. 
- $f(2, 3) = A_{2} + max(A_{2}, A_{3}) = 2 + max(2, 3) = 2 + 3 = 5$.
- $f(3, 3) = A_{3} = 3$. 

Hence the required sum $= 1 + 3 + 6 + 2 + 5 + 3 = 20$.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Data structures


Solutions:
from collections import deque
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	arr = [0] + list(map(int, input().strip().split()))
	dp = [0] * (n + 5)
	ans = 0
	stk = deque()
	for i in range(n, 0, -1):
		while stk and arr[i] > arr[stk[-1]]:
			stk.pop()
		ind = n + 1
		if stk:
			ind = stk[-1]
		stk.append(i)
		tmp1 = (n + 1) * (ind - i) % mod
		tmp2 = (ind * (ind - 1) // 2 - i * (i - 1) // 2) % mod
		tmp = arr[i] * (tmp1 - tmp2) % mod
		tmp = (tmp + mod) % mod
		dp[i] = (tmp + dp[ind]) % mod
		ans += dp[i]
		ans %= mod
	print(ans)


inf = float('inf')
import sys
import pprint
import logging
from logging import getLogger
import array

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')
mod = int(1000000000.0) + 7

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

def add(a, b):
	a %= mod
	b %= mod
	return ((a + b) % mod + mod) % mod

def solve():
	(n,) = maps()
	a = [0] + list(maps())
	ngr = [n + 1] * (n + 1)
	st = [[inf, inf]]
	for i in range(1, n + 1):
		while a[i] >= st[-1][0]:
			ngr[st[-1][1]] = i
			st.pop()
		st.append([a[i], i])
	dp = [0] * (n + 2)
	i = n
	while i >= 0:
		num = ngr[i] - i
		dp[i] = mul(a[i], num * (num + 1) // 2)
		dp[i] = add(dp[i], mul(num * a[i], n - ngr[i] + 1))
		dp[i] = add(dp[i], dp[ngr[i]])
		i -= 1
	ans = 0
	for i in range(1, n + 1):
		ans = add(ans, dp[i])
	print(ans)
for _ in range(*maps()):
	solve()


import sys
import bisect
input = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
sys.setrecursionlimit(10 ** 6)
flsh = lambda : sys.stdout.flush()
sa = lambda : input()
sb = lambda : int(input())
sc = lambda : input().split()
sd = lambda : list(map(int, input().split()))
se = lambda : float(input())
sf = lambda : list(input())
mod = 10 ** 9 + 7

def hnbhai():
	n = sb()
	a = sd()
	right = []
	s = []
	pre = [0] * (n + 1)
	for i in range(1, n + 1):
		pre[i] = n - i + 1
		pre[i] += pre[i - 1]
		pre[i] %= mod
	for i in range(n - 1, -1, -1):
		while len(s) > 0 and a[s[-1]] < a[i]:
			s.pop()
		if len(s) == 0:
			right.append(n)
		else:
			right.append(s[-1])
		s.append(i)
	right.reverse()
	ans = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		ans[i] = a[i] * (pre[right[i]] - pre[i])
		ans[i] += ans[right[i]]
		ans[i] %= mod
	print(sum(ans) % mod)
for _ in range(sb()):
	hnbhai()


import sys
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
sys.setrecursionlimit(10 ** 8)
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
mod1 = 998244353
for _ in range(ii()):
	n = ii()
	a = il()
	right = []
	s = []
	for i in range(n - 1, -1, -1):
		while len(s) > 0 and a[s[-1]] <= a[i]:
			s.pop()
		if len(s) == 0:
			right.append(n)
		else:
			right.append(s[-1])
		s.append(i)
	right.reverse()
	left = []
	s = []
	for i in range(n):
		while len(s) > 0 and a[s[-1]] < a[i]:
			s.pop()
		if len(s) == 0:
			left.append(-1)
		else:
			left.append(s[-1])
		s.append(i)
	ans = 0
	for i in range(n):
		x = i - left[i]
		y = right[i] - i
		z = n - right[i]
		t = y * (y + 1) // 2
		t1 = y * z
		t2 = t + t1
		tot = t2 * x
		ans += tot * a[i]
		ans %= mod
	print(ans)


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7

def add(a, b):
	return (a % mod + b % mod) % mod

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

def solve(i):
	if i == n:
		return 0
	if dp[i] != -1:
		return dp[i]
	m = nind[i] - i
	x = mul(mul(m, m + 1), 500000004)
	x = mul(x, a[i])
	v = mul(mul(m, a[i]), n - nind[i])
	val = add(add(x, v), solve(nind[i]))
	dp[i] = val
	return val

def answer():
	s = []
	for i in range(n):
		while len(s) and a[s[-1]] < a[i]:
			nind[s[-1]] = i
			s.pop()
		s.append(i)
	ans = 0
	for i in range(n):
		ans = add(ans, solve(i))
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	nind = [n] * n
	dp = [-1] * n
	print(answer())