Polygon Game

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka are experienced skaters. They don’t want to just skate around, so they came up with the following game.

Before the game starts, Zenyk virtuously draws a convex \(n\)-gon on the ice with his skates.

When the polygon is ready, the players take turns. Marichka goes first.

In one turn, a player can choose a diagonal of the polygon and skate along it, cutting the ice. The diagonal will split the polygon into two smaller polygons. Then the player chooses one of the two parts on which the game will continue. This ends the turn.

The game ends when a triangle remains.

Marichka wants to maximize the area of the remaining triangle, and Zenyk wants to minimize it.

What will the area be under optimal play by both players?

Input

The first line contains an integer \(n\) — the number of vertices of the polygon.

The next \(n\) lines contain two integers \(x_i\), \(y_i\) each — the coordinates of the vertices of the polygon in counterclockwise order.

Output

Print an integer — twice the area of the triangle remaining after the game ends.

It can be proven that twice the area of a triangle with integer coordinates is an integer.

Constraints

\(4 \le n \le 10^5\),

\(|x_i|, |y_i| \le 10^9\),

no three vertices of the polygon are collinear.

7 points: \(n \le 15\);

8 points: \(n \le 10^3\);

10 points: no additional constraints.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 0 0 7 4 3 11 -4 7	65

Input (stdin) сopy	Output (stdout) сopy
20 -20 5 -20 1 -19 -3 -17 -7 -15 -9 -13 -10 -11 -10 5 -8 12 -7 15 -6 17 -4 18 -1 18 3 17 6 15 8 12 9 8 9 -5 8 -14 7 -19 6	4

Notes

In the first example, the game will end after Marichka’s first move. Regardless of which diagonal she chooses, the square will be divided into two equal triangles.

In the second example, one of the possible scenarios is as follows. Marichka cuts the diagonal between the vertices \((-15, -9)\) and \((5, -8)\) (purple) and leaves the upper part for the game. Zenyk draws the diagonal between the vertices \((-20, 5)\) and \((-19, -3)\) (green) and leaves the triangle. The game ends here.