For the first time, breakdance will be featured in the Olympics. And you get to participate! Well, you get to participate to the jury... More precisely, you get to build the table in front of which the jury will be seated: still, that is an impressive feat, congratulations!
Actually, the top of the table is already built: it is plane, has constant width and constant density, and its shape consists in the interior of an $$$N$$$-sided non-crossing polygon $$$P_1 P_2 \dots P_N$$$ in which no three vertices are collinear (i.e., no line goes through three vertices or more). You have three table legs of same length and negligible width. Your task is to place them at distinct corners of the table so that the table remains stable when standing on these legs. In other words, you must choose three vertices $$$P_i$$$, $$$P_j$$$ and $$$P_k$$$ of the polygon such that the centre of gravity of the polygon lies in the interior of the triangle $$$P_i P_j P_k$$$ (and not on its boundary).
In how many different ways can you do this? If two ways of placing legs differ only by a permutation of the legs, they are not counted as different ways.
The first line contains the number $$$N$$$. Then follow $$$N$$$ lines: the $$$i^\text{th}$$$ of these lines contains two space-separated integers $$$x_i$$$ and $$$y_i$$$, which are the $$$x$$$-coordinate and the $$$y$$$-coordinate of the vertex $$$P_i$$$.
Limits
- $$$3 \leq N \leq 100~000$$$;
- $$$-1~000~000 \leq x_i \leq 1~000~000$$$ and $$$-1~000~000 \leq y_i \leq 1~000~000$$$ for all $$$i \leq N$$$;
- whenever $$$1 \leq i < j < k \leq N$$$, the vertices $$$P_i$$$, $$$P_j$$$ and $$$P_k$$$ are not collinear;
- the polygonal shape $$$P_1 P_2 \dots P_N$$$ is non-crossing.
The output should contain a single line, consisting of a single integer: the number of ways of placing legs such that the table remains stable.
4 0 0 1 0 1 1 0 1
0
4 0 0 5 0 6 6 0 5
1
5 0 0 2 0 2 20 1 1 0 20
5
