Олимпиадный тренинг

Задача . F. Великолепный прыжок


Вам дан массив натуральных чисел \(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\).

Примечание

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

  • Из \(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\).


Примеры
№Входные данныеВыходные данные
1
3
2 1 3
0 1 2
2
6
1 4 1 6 3 2
0 1 2 3 6 8
3
2
1 2
0 1
4
4
1 4 4 4
0 1 4 8
Статистика успешных решений по компиляторам
 Кол-во
С++5