Recently, Vadim threw N points onto a plane with Cartesian coordinates. All the points scattered everywhere. Therefore, Vadim decided to bring order.

First, he took the highest point (the point with the greatest ordinate) and called it the delegate of all the points. After that, he constructed the convex hull of all N points. Then he selected all the points to the left of the delegate (points with a smaller abscissa) and separated them into a distinct set. He did the same with all the points to the right of the delegate (points with a greater abscissa). Vadim then repeated the same procedure for each of these sets recursively. If any set turned out to be empty, Vadim skipped it.

As a result, each point served as a delegate for some set of points, and for each of these sets, Vadim constructed a convex hull. Due to the properties of the convex hull, each of them is either a point, a segment, or a convex polygon. We will denote the size of the convex hull for a point as 1, for a segment as 2, and for a convex polygon as the number of vertices of that polygon.

Find the size of the convex hull of the set for each given point for which it is the delegate.

The first line contains an integer N — the number of points thrown by Vadim (1 ≤ N ≤ 10⁵).

In the following N lines, two integers x_i and y_i are given — the abscissa and ordinate of the i-th point (|x_i|, |y_i| ≤ 10⁹). It is guaranteed that all abscissas are distinct and all ordinates are distinct.

Output N integers l_i — the size of the convex hull of the set for which the i-th point is the delegate.