CF1901F.Landscaping

You are appointed to a very important task: you are in charge of flattening one specific road.

The road can be represented as a polygonal line starting at $(0, 0)$, ending at $(n - 1, 0)$ and consisting of $n$ vertices (including starting and ending points). The coordinates of the $i$-th vertex of the polyline are $(i, a_i)$.

"Flattening" road is equivalent to choosing some line segment from $(0, y_0)$ to $(n - 1, y_1)$ such that all points of the polyline are below the chosen segment (or on the same height). Values $y_0$ and $y_1$ may be real.

You can imagine that the road has some dips and pits, and you start pouring pavement onto it until you make the road flat. Points $0$ and $n - 1$ have infinitely high walls, so pavement doesn't fall out of segment $[0, n - 1]$.

The cost of flattening the road is equal to the area between the chosen segment and the polyline. You want to minimize the cost, that's why the flattened road is not necessary horizontal.

But there is a problem: your data may be too old, so you sent a person to measure new heights. The person goes from $0$ to $n - 1$ and sends you new heights $b_i$ of each vertex $i$ of the polyline.

Since measuring new heights may take a while, and you don't know when you'll be asked, calculate the minimum cost (and corresponding $y_0$ and $y_1$) to flatten the road after each new height $b_i$ you get.

你被委派了一项非常重要的任务：负责平整某一条特定的道路。

该道路可表示为一条折线，起点为 $(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$，并依次向你发送每个顶点 $i$ 的新高度 $b_i$。

由于测量新高度可能耗时较长，且你无法预知何时会收到查询请求，因此你需要在每次接收到一个新高度 $b_i$ 后，立即计算出此时平整道路的最小成本（以及对应的 $y_0$ 和 $y_1$）。

The first line contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of vertices of the polyline.

The second line contains $n$ integers $a_0, a_1, \dots, a_{n - 1}$ ($0 \le a_i \le 10^9$; $a_0 = a_{n - 1} = 0$) — the heights of the corresponding vertices.

The third line contains $n$ integers $b_0, b_1, \dots, b_{n - 1}$ ($0 \le b_i \le 10^9$; $b_0 = b_{n - 1} = 0$) — the new heights of the corresponding vertices.

第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）—— 折线的顶点数量。

第二行包含 $n$ 个整数 $a_0, a_1, \dots, a_{n - 1}$（$0 \le a_i \le 10^9$；且 $a_0 = a_{n - 1} = 0$）—— 对应顶点的原始高度。

第三行包含 $n$ 个整数 $b_0, b_1, \dots, b_{n - 1}$（$0 \le b_i \le 10^9$；且 $b_0 = b_{n - 1} = 0$）—— 对应顶点的目标高度。

Print $n$ numbers: as the $i$-th number ($0$-indexed) print $y_0 + y_1$ of the "best segment" (i. e. the sum of coordinates of the segment that gives the minimum cost) if you already know actual heights $b_0, \dots, b_i$.

If there are several "best segments", print the minimum possible $y_0 + y_1$ among them.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-9}$.

Formally, let your answer be $x$, and the jury's answer be $y$. Your answer is accepted if and only if $\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-9}$.

输出 $n$ 个数：对于第 $i$ 个数（下标从 $0$ 开始），在已知实际高度 $b_0, \dots, b_i$ 的前提下，输出“最优线段”（即给出最小代价的线段）的 $y_0 + y_1$ 值。

若存在多个“最优线段”，则输出其中最小的 $y_0 + y_1$ 值。

当你的答案的绝对误差或相对误差不超过 $10^{-9}$ 时，即视为正确。

形式化地，设你的答案为 $x$，评测机的答案为 $y$。当且仅当 $\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-9}$ 时，你的答案被接受。

The first answer in the first example is shown on the picture above.

You can achieve the second answer with the following "best segment":

You can achieve the third answer using the following "best segment":

You can achieve the fourth answer with the "best segment" shown below:

第一个示例中的第一个答案如上图所示。

你可以通过以下“最优线段”得到第二个答案：

你可以通过以下“最优线段”得到第三个答案：

你可以通过下图所示的“最优线段”得到第四个答案：