147. Triangulation Rocks the Nation Again
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
This problem is worth 60 points.

This is a sigificantly harder version of a previous problem in the contest. We recommend you solve the earlier problem first.

You're given the coordinates of an $$$n$$$-sided polygon. The polygon is not necessarily a regular polygon (the sides and angles are not necessarily equal), but the polygon is guaranteed to be convex (the polygon will not contain any angles greater than or equal to 180 degrees).

Given this information, figure out the area of the given polygon.

Input

The first line of input consists of a positive integer $$$n$$$ greater than three: the number of sides of the polygon.

The next $$$n$$$ lines each contain two space-separated integers: the $$$x$$$ and $$$y$$$ coordinates of each point of the polygon.

None of the sides of the polygon will be completely vertical.

Output

Output a single decimal number $$$a$$$: the area of the given $$$n$$$-sided polygon. Remember, the polygon is guaranteed to be a convex polygon.

Examples
Input
4
0 5
5 0
0 -5
-5 0
Output
50.0
Input
5
6 6
4 3
2 1
1 5
3 7
Output
15.5
Input
4
1 1
2 3
3 6
4 9
Output
1.0
Note

It might help to use your code from the easier version