_Poor them!_
Whenever rain season comes, the water rises as hell and the most affected region is Northwest Vietnam. Villages, houses, plants, animals, and people are all victims of cruel Nature.
S_e_o is a civil manager of Northwest Vietnam. As a man with a kind heart, he worries for Northwestern citizens and is willing to do everything to stop the disaster. With only a computer, he roughly models the area of Northwest Vietnam on Cartesian plane. The model is a polyline with n points, each with integer coordinates. He wants to calculate the maximum area that could be filled with water, but his computer breaks down right after he has finished the model. He still keeps the input data and calls for your help!
Please help him !!
The first line contains an integer $" "n " "(2 <= n <= 10^5)$ , the number of points in the polyline
Line 2..$" "n + 1$ : Line $i$ contains two numbers $x_i, " "y_i (0 <= x_i, " "y_i <= 10^6)$ which are x-coordinates and y-coordinates of a point.
It is guaranteed that $x_i < x_{i + 1}$
Output: A single line contains a single real number which is the answer. Your output is correct if the difference between your output and the test answer is no larger than $10^(-6)$
The following image explains the first sample test case
## Input
The first line contains an integer $" "n " "(2 <= n <= 10^5)$ , the number of points in the polylineLine 2..$" "n + 1$ : Line $i$ contains two numbers $x_i, " "y_i (0 <= x_i, " "y_i <= 10^6)$ which are x-coordinates and y-coordinates of a point. It is guaranteed that $x_i < x_{i + 1}$
## Output
Output: A single line contains a single real number which is the answer. Your output is correct if the difference between your output and the test answer is no larger than $10^(-6)$
[samples]
## Note
The following image explains the first sample test case
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of points in the polyline.
Let $ P = \{(x_i, y_i) \mid i \in \{1, \dots, n\}\} $ be the sequence of points with integer coordinates, where $ x_i < x_{i+1} $ for all $ i $.
**Constraints**
1. $ 2 \leq n \leq 10^5 $
2. $ 0 \leq x_i, y_i \leq 10^6 $ for all $ i \in \{1, \dots, n\} $
3. $ x_i < x_{i+1} $ for all $ i \in \{1, \dots, n-1\} $
**Objective**
Compute the maximum area bounded above by the polyline and below by the "water level" formed by connecting each point to the minimum height between its left and right neighbors, i.e., the area under the polyline but above the "filling" level defined by:
For each segment $ [x_i, x_{i+1}] $, the water surface is at height $ \min(y_i, y_{i+1}) $, and the area is the integral of $ \max(0, y_i - \min(y_i, y_{i+1}), y_{i+1} - \min(y_i, y_{i+1})) $ — but more precisely, the area between the polyline and the *lower envelope* formed by local minima.
Actually, the correct interpretation:
The water fills to the level of the *lower of the two endpoints* of each segment, and the area is the sum over all segments of the trapezoid above that level but below the polyline.
But standard interpretation in such problems:
The area of water that can be held is the area *under* the polyline and *above* the "filling curve" which is the *lower envelope* formed by connecting each point to the minimum of its adjacent heights — but this is equivalent to computing the area between the polyline and the "water surface" that is the *minimum of the prefix maximum and suffix maximum* at each point.
Actually, standard solution:
For each point $ i $, define:
- $ L_i = \max\{y_1, y_2, \dots, y_i\} $ (prefix maximum)
- $ R_i = \max\{y_i, y_{i+1}, \dots, y_n\} $ (suffix maximum)
Then the water level at point $ i $ is $ h_i = \min(L_i, R_i) $, and the water area is the area between the polyline $ y_i $ and the water level $ h_i $, integrated over $ x $.
But since it's a polyline, we compute the area between the water surface (piecewise linear between $ h_i $) and the ground (polyline), which is:
$$
\text{Area} = \sum_{i=1}^{n-1} \frac{(x_{i+1} - x_i)}{2} \cdot \left[ (h_i - y_i) + (h_{i+1} - y_{i+1}) \right]
$$
But only if $ h_i \ge y_i $ and $ h_{i+1} \ge y_{i+1} $, which they are by construction.
Actually, the water surface is the "skyline" defined by $ h_i = \min(\text{prefix\_max}_i, \text{suffix\_max}_i) $, and the area is:
$$
\sum_{i=1}^{n-1} \left( \frac{(x_{i+1} - x_i)}{2} \cdot \left( (h_i - y_i) + (h_{i+1} - y_{i+1}) \right) \right)
$$
But note: if $ h_i = y_i $, then no water above that point.
So formally:
**Objective**
Define:
- $ L_i = \max_{1 \le j \le i} y_j $
- $ R_i = \max_{i \le j \le n} y_j $
- $ h_i = \min(L_i, R_i) $ for each $ i \in \{1, \dots, n\} $
Compute the total water area:
$$
\text{Area} = \sum_{i=1}^{n-1} \frac{x_{i+1} - x_i}{2} \cdot \left( (h_i - y_i) + (h_{i+1} - y_{i+1}) \right)
$$