E. Largest Triangle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a convex polygon, you are required to find the triangle with the largest area among all triangles whose vertices coincide with the vertices of the polygon.

Input

The input consists of no more than $$$50$$$ test cases. The first line of each test case contains an integer $$$n$$$, representing the number of vertices of the polygon ($$$3 \le n \le 20,000$$$). Each of the next $$$n$$$ lines contains two integers ranging from $$$-10^9$$$ to $$$10^9$$$, representing the coordinates of the vertices. It is guaranteed that the given polygon is non-degenerate and strictly convex, meaning it is convex and no three of its vertices lie on the same line. The vertices are enumerated in counterclockwise order. The input is terminated by a line containing a single zero, which should not be processed. The tests are generated with some kind of random.

Output

For each test case, output a single positive integer, which is equal to twice the area of the required triangle. It can be easily proved that these numbers are always integers.

Example
Input
4
-1 -1
1 -1
2 1
0 1
5
0 0
5 0
5 2
2 4
0 2
0
Output
4
20