Very Visible Point Pairs

At first, the coordinate plane contains no points. N points are added one by one in the given order. Every point has integer coordinates, no two points have the same x-coordinate, and no two points have the same y-coordinate.

For two different points A and B, let R(A,B) be the unique axis-aligned rectangle whose diagonal has A and B as its endpoints. If no other currently added point lies inside R(A,B), then A and B form a very visible pair. The pairs (A,B) and (B,A) are the same pair and are counted once.

After each point is added, compute the number of very visible pairs among all points added so far.

The first line contains an integer N, the number of points. (2 <= N <= 5000)

Each of the next N lines contains two integers X and Y, the coordinates of a point, in the order the points are added. The coordinates satisfy 0 <= X, Y <= 1000000. No two points have the same x-coordinate, and no two points have the same y-coordinate.

Print N lines. The k-th line must contain the number of very visible pairs after the first k points have been added.