F. Великолепный прыжок
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
128 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив натуральных чисел $$$a_1,a_2,\ldots,a_n$$$ длины $$$n$$$.

За одну операцию вы можете прыгнуть с позиции $$$i$$$ на позицию $$$j$$$ ($$$1 \le i \le j \le n$$$), заплатив $$$\min(a_i, a_{i + 1}, \ldots, a_j) \cdot (j - i)^2$$$ эрисов.

Для каждого $$$k$$$ от $$$1$$$ до $$$n$$$ найдите минимальное количество эрисов, которое вам придется потратить, чтобы добраться от позиции $$$1$$$ до позиции $$$k$$$.

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

Первая строка содержит одно число $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$) — длину массива.

Во второй строке содержится $$$n$$$ чисел $$$a_1,a_2,\ldots a_n$$$ ($$$1 \le a_i \le n$$$).

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

Выведите $$$n$$$ чисел, $$$k$$$-е из которых является минимальным количеством эрисов, которое вам придется потратить, чтобы добраться от позиции $$$1$$$ до позиции $$$k$$$.

Примеры
Входные данные
3
2 1 3
Выходные данные
0 1 2
Входные данные
6
1 4 1 6 3 2
Выходные данные
0 1 2 3 6 8
Входные данные
2
1 2
Выходные данные
0 1
Входные данные
4
1 4 4 4
Выходные данные
0 1 4 8
Примечание

В первом тесте:

  • Из $$$1$$$ в $$$1$$$: стоимость $$$0$$$,
  • Из $$$1$$$ в $$$2$$$: $$$1 \rightarrow 2$$$ - стоимость $$$\min(2, 1) \cdot (2 - 1) ^ 2=1$$$,
  • Из $$$1$$$ в $$$3$$$: $$$1 \rightarrow 2 \rightarrow 3$$$ - стоимость $$$\min(2, 1) \cdot (2 - 1) ^ 2 + \min(1, 3) \cdot (3 - 2) ^ 2 = 1 + 1 = 2$$$.

В четвертом тесте из $$$1$$$ в $$$4$$$: $$$1 \rightarrow 3 \rightarrow 4$$$ - стоимость $$$\min(1, 4, 4) \cdot (3 - 1) ^ 2 + \min(4, 4) \cdot (4 - 3) ^ 2 = 4 + 4 = 8$$$.