Вам дан массив натуральных чисел \(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\) в \(4\): \(1 \rightarrow 3 \rightarrow 4\) - стоимость \(\min(1, 4, 4) \cdot (3 - 1) ^ 2 + \min(4, 4) \cdot (4 - 3) ^ 2 = 4 + 4 = 8\).
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
4000 ms 128 Mb Правила оформления программ и список ошибок при автоматической проверке задач