codeforces#P1988E. Range Minimum Sum

    ID: 34774 远端评测题 4000ms 512MiB 尝试: 1 已通过: 0 难度: 10 上传者: 标签>binary searchbrute forcedata structuresimplementation

Range Minimum Sum

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

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

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

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

4
1
1
3
3 1 2
5
4 2 1 5 3
8
8 1 4 6 7 3 5 2
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$.