CF1988E Range Minimum Sum

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

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