Description:
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 Format:
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 Format:
For each test case, print one line containing $$$n$$$ integers. The $$$i$$$-th integer should be the answer when erasing $$$a_i$$$.
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$$$.