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