Вас назначили на очень важное дело: подготовиться к выравниванию одной особой дороги.
Дорогу можно представить как ломаную линию, начинающуюся в \((0, 0)\) и заканчивающуюся в \((n - 1, 0)\), которая состоит из \(n\) вершин (включая стартовую и финишную). Координаты \(i\)-й вершины ломаной равны \((i, a_i)\).
«Выравнивание» дороги эквивалентно выбору некоторого отрезка из \((0, y_0)\) в \((n - 1, y_1)\) такого, что все точки ломаной находятся ниже выбранного отрезка (или на той же высоте). Значения \(y_0\) и \(y_1\) могут быть действительными числами.
Вы можете представить, что первоначально на дороге есть всякие ямы и ухабы, и вы начинаете насыпать на нее покрытие, пока не сделаете ее ровной. Для простоты, в точках \(0\) и \(n - 1\) находятся бесконечно высокие стены, а потому покрытие не вываливается наружу отрезка \([0, n - 1]\).
Цена выровненной дороги равна площади между выбранным отрезком и ломаной. Вы хотите минимизировать эту цену, а потому выровненная дорога будет необязательно горизонтальной.
Но есть одна проблема: ваша информация могла устареть. А потому вы отправили специального человека померить новые высоты. Этот человек идет из \(0\) в \(n - 1\) и посылает вам новые высоты \(b_i\) для каждой вершины \(i\) ломаной.
Так как подсчет новых высот может занять много времени, а вы не знаете, когда вас попросят отчитаться, посчитайте наименьшую цену (и соответствующие \(y_0\) и \(y_1\)) для выравнивания дороги после получения каждого нового значения \(b_i\).
Выходные данные
Выведите \(n\) чисел: \(i\)-м числом (\(0\)-индексация) выведите \(y_0 + y_1\) «лучшего отрезка» (т. е. сумму координат отрезка, который имеет минимальную цену), если вы уже знаете новые значения высот \(b_0, \dots, b_i\).
Если существует несколько «лучших отрезков», выведите наименьшее возможное значение \(y_0 + y_1\).
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит \(10^{-9}\).
Формально, пусть ваш ответ равен \(x\), а ответ жюри равен \(y\). Ваш ответ будет зачтен, если и только если \(\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-9}\).
Примечание
Первый ответ на первый пример изображен выше.
Вы можете получить второй ответ, выбрав следующий «лучший отрезок»:
Вы можете достигнуть третий ответ, используя следующий «лучший отрезок»:
Вы можете получить четвертый ответ следующим образом:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
0 5 1 3 0
0 1 3 2 0
|
8.000000000000 4.000000000000 6.000000000000 6.000000000000 6.000000000000
|
|
2
|
6
0 4 1 3 3 0
0 1 4 0 1 0
|
7.000000000000 5.000000000000 7.500000000000 7.500000000000 6.666666666667 6.666666666667
|