E. Range Minimum Sum
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

For an array $$$[a_1,a_2,\ldots,a_n]$$$ of length $$$n$$$, define $$$f(a)$$$ as the sum of the minimum element over all subsegments. That is, $$$$$$f(a)=\sum_{l=1}^n\sum_{r=l}^n \min_{l\le i\le r}a_i.$$$$$$

A permutation is a sequence of integers from $$$1$$$ to $$$n$$$ of length $$$n$$$ containing each number exactly once. You are given a permutation $$$[a_1,a_2,\ldots,a_n]$$$. For each $$$i$$$, solve the following problem independently:

  • Erase $$$a_i$$$ from $$$a$$$, concatenating the remaining parts, resulting in $$$b = [a_1,a_2,\ldots,a_{i-1},\;a_{i+1},\ldots,a_{n}]$$$.
  • Calculate $$$f(b)$$$.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1\le n\le 5\cdot 10^5$$$).

The second line of each test case contains $$$n$$$ distinct integers $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print one line containing $$$n$$$ integers. The $$$i$$$-th integer should be the answer when erasing $$$a_i$$$.

Example
Input
4
1
1
3
3 1 2
5
4 2 1 5 3
8
8 1 4 6 7 3 5 2
Output
0 
4 7 5 
19 21 27 17 19 
79 100 72 68 67 80 73 80
Note

In the second test case, $$$a=[3,1,2]$$$.

  • When removing $$$a_1$$$, $$$b=[1,2]$$$. $$$f(b)=1+2+\min\{1,2\}=4$$$.
  • When removing $$$a_2$$$, $$$b=[3,2]$$$. $$$f(b)=3+2+\min\{3,2\}=7$$$.
  • When removing $$$a_3$$$, $$$b=[3,1]$$$. $$$f(b)=3+1+\min\{3,1\}=5$$$.