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