Triangle Hull#13017

Triangle Hull

3 seconds
512 megabytes
Very hard

There are points p_i on a two-dimensional plane, with p_i located at coordinates (x_i, y_i). It is guaranteed that no two points occupy the same position, and no three points are collinear.

Find the number of ways to choose three points from the given set such that the convex hull of any subset containing these three points is a triangle.

Input

The first line contains an integer – the number of points.

Each of the next lines contains two integers x_i and y_i – the coordinates of p_i.

3 \le n \le 2000,

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

no two points are at the same location,

no three points are collinear.

Output

Output a single integer – the number of ways to choose three points from the given set such that the convex hull of any subset containing these three points is a triangle.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

The given points in the first sample are arranged as shown in the figure below.

In the first sample, the following two ways to choose three points satisfy the condition:

  • \{p_1, p_4, p_6\},

  • \{p_2, p_4, p_6\}.

The given points in the second sample are arranged as shown in the figure below.

In the second sample, the following four ways to choose three points satisfy the condition:

  • \{p_1, p_2, p_3\},

  • \{p_1, p_2, p_4\},

  • \{p_1, p_3, p_4\},

  • \{p_2, p_3, p_4\}.