E. Сумма минимумов на подотрезках
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива $$$[a_1,a_2,\ldots,a_n]$$$ длины $$$n$$$ определим $$$f(a)$$$ как сумму минимального элемента по всем подотрезкам этого массива. Иными словами, $$$$$$f(a)=\sum_{l=1}^n\sum_{r=l}^n \min_{l\le i\le r}a_i.$$$$$$

Перестановка — это последовательность целых чисел от $$$1$$$ до $$$n$$$ длиной $$$n$$$, содержащая каждое число ровно один раз. Вам дана перестановка $$$[a_1,a_2,\ldots,a_n]$$$. Для каждого $$$i$$$ решите следующую задачу независимо:

  • Удалите $$$a_i$$$ из $$$a$$$, объединив оставшиеся части, получив $$$b = [a_1,a_2,\ldots,a_{i-1},\;a_{i+1},\ldots,a_{n}]$$$.
  • Вычислите $$$f(b)$$$.
Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^5$$$). Затем следует описание наборов.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1\le n\le 5\cdot 10^5$$$).

Вторая строка каждого набора содержит $$$n$$$ различных целых чисел $$$a_1,\ldots,a_n$$$ ($$$1\le a_i\le n$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$10^6$$$.

Выходные данные

Для каждого набора выведите одну строку, содержащую $$$n$$$ целых чисел. $$$i$$$-е целое число должно быть ответом при удалении $$$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
Примечание

Во втором наборе входных данных $$$a=[3,1,2]$$$.

  • При удалении $$$a_1$$$, $$$b=[1,2]$$$. $$$f(b)=1+2+\min\{1,2\}=4$$$.
  • При удалении $$$a_2$$$, $$$b=[3,2]$$$. $$$f(b)=3+2+\min\{3,2\}=7$$$.
  • При удалении $$$a_3$$$, $$$b=[3,1]$$$. $$$f(b)=3+1+\min\{3,1\}=5$$$.