M. Almost Convex
time limit per test
1 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is a story about Kevin, a friend of Little Cyan Fish.

Kevin is the chief judge of the International Convex Polygon Championship (ICPC). He proposed a geometry task for the contest. However, since he is inexperienced in computational geometry, he couldn't generate a correct convex polygon for the tests of the task.

Kevin was very saddened by this. His good friend, Little Cyan Fish, consoled him by saying, "Although the data you generated is not a convex polygon, you can call it an almost-convex polygon!"

Given a set of points $$$S$$$ (containing at least $$$3$$$ points) in a two-dimensional plane, where no two points coincide and no three points are collinear. Little Cyan Fish calls a polygon $$$P$$$ an almost-convex polygon, if and only if:

  • The polygon $$$P$$$ is simple, i.e., its vertices are distinct and no two edges of the polygon intersect or touch, except that consecutive edges touch at their common vertex.
  • The vertices of the polygon belong to $$$S$$$, and all points in $$$S$$$ are either inside or on the boundary of the polygon.

Let $$$\mathbb{U}$$$ be the set consisting of all almost-convex polygons. It can be shown that $$$\mathbb{U}$$$ is a finite set and is not empty. Therefore, there exists a polygon $$$R$$$ such that $$$|R|$$$ is the minimum among all polygons in $$$\mathbb{U}$$$ ($$$|R|$$$ is the number of vertices of polygon $$$R$$$).

Kevin and Little Cyan Fish want you to calculate the number of polygons $$$Q \in \mathbb{U}$$$ such that $$$|Q| \le |R| + 1$$$.

Input

There is only one test case in each test file.

The first line contains an integer $$$n$$$ ($$$3 \le n \le 2 \times 10^3$$$) indicating the number of points in set $$$S$$$.

For the following $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^6 \le x_i, y_i \le 10^6$$$) indicating a point $$$(x_i, y_i)$$$ in set $$$S$$$.

It is guaranteed that no two points in $$$S$$$ coincide and no three points are collinear.

Output

Output one line containing one integer indicating the number of polygons $$$Q$$$.

Examples
Input
7
1 4
4 0
2 3
3 1
3 5
0 0
2 4
Output
9
Input
5
4 0
0 0
2 1
3 3
3 1
Output
5
Input
3
0 0
3 0
0 3
Output
1
Note

For the first sample test case, $$$|R| = 4$$$. All polygons $$$Q$$$ are shown below.

For the second sample test case, $$$|R| = 3$$$. All polygons $$$Q$$$ are shown below.