Convex Hull

The convex hull of a 2-dimensional point set $P$ is the polygon with the smallest perimeter that encloses all points in $P$. It is called convex because the polygon always has a convex shape.

You are given a set $P$ of $N$ points. For each point $(x_i, y_i) \in P$, output the number of points in $P \setminus \{(x_i, y_i)\}$ that lie exactly on the convex hull of $P \setminus \{(x_i, y_i)\}$. In other words, point $(x_i, y_i)$ is removed from $P$ before the hull is built. The hull can degenerate into a line segment or a single point, depending on the points.

The first line contains an integer $N$ ($2 \le N \le 100000$), the number of points in $P$. Each of the next $N$ lines contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), the coordinates of the $i$th point. No two points share the same coordinates.

Print $N$ lines. The $i$th line contains the number of points in $P \setminus \{(x_i, y_i)\}$ that lie exactly on the convex hull of $P \setminus \{(x_i, y_i)\}$.