B. Minimal Area
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a strictly convex polygon. Find the minimal possible area of non-degenerate triangle whose vertices are the vertices of the polygon.

Input

The first line contains a single integer n (3 ≤ n ≤ 200000) — the number of polygon vertices.

Each of the next n lines contains two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of polygon vertices.

The polygon is guaranteed to be strictly convex. Vertices are given in the counterclockwise order.

Output

It is known that the area of triangle whose vertices are the integer points on the grid is either integer or half-integer.

Output a single integer — the required area, multiplied by 2.

Examples
Input
4
0 1
3 0
3 3
-1 3
Output
5
Input
3
0 0
1 0
0 1
Output
1
Input
4
-999999991 999999992
-999999993 -999999994
999999995 -999999996
999999997 999999998
Output
3999999948000000156
Note

It is recommended to make all calculations using integer numbers, because floating point precision most likely would not be enough.