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$$$.

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$$$.

Range Minimum Sum

Examples