Для массива \([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\) решите следующую задачу независимо:
Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных \(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\).
Во втором наборе входных данных \(a=[3,1,2]\).
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
4000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач