Polygon — Eolymp

Input

The first line contains the integer $n$ ( $3 \leq n \leq 100000$ 3 \leq n \leq 100\,000), representing the number of vertices. Each of the following $n$ lines contains two integers, which are the coordinates of the polygon's vertices ( $- 5 \cdot 1 0^{8} \leq x, y \leq 5 \cdot 1 0^{8}$ -5 \cdot 10^8 \leq x, y \leq 5 \cdot 10^8). The coordinates are provided in either a clockwise or counterclockwise sequence.

Output

Output a single number with a precision of $3$ decimal places, representing the total length of the grid line segments that lie strictly within the polygon.

Examples

Example 1

Loading

Note

Explanation of the first test

Total length of horizontal lines: $4/3 + 8/3 = 4$ 4/3 + 8/3 = 4
Total length of vertical lines: $3 + 2 + 1 = 6$ 3 + 2 + 1 = 6
Therefore, the total length is $4 + 6 = 10$ 4 + 6 = 10

Explanation of the second test

Total length of horizontal lines: $1 + 2 + 4 = 7$ 1 + 2 + 4 = 7
Total length of vertical lines: $9/4 + 3/2 + 7/4 = 5.5$ 9/4 + 3/2 + 7/4 = 5.5
Therefore, the total length is $7 + 5.5 = 12.5$ 7 + 5.5 = 12.5