N points are given in a plane. Any point has integer coordinates and no two points have the same x coordinates or the same y coordinates. A pair of points A and B uniquely define a rectangle R(A,B) whose sides are parallel to coordinate axes such that the points A and B are endpoints of one of its diagonals. A pair of two given points A and B are very visible if there are no other given points within a rectangle R(A,B). A pair of points consists of two different points and in this problem pairs (A,B) and (B,A) are regarded to be the same pair and are counted as one pair.

At the beginning a coordinate plane has no given points. Your program should read coordinates of the given points and after reading coordinates of a point, it should write number of pairs of currently very visible given points.

Input

First line of input contains an integer N, 2 ≤ N ≤ 5000, the number of given points. Each of the following N lines contains two integers X, Y, 0 ≤ X,Y ≤ 10^6, coordinates of the given points in the order they should be added to the plane.

Output

An output should contain N lines, kth line should contain a number of pairs of very visible given points after taking kth given point into account.

Sample

input
7
1 5
2 7
3 8
5 1
6 2
7 3
4 4

output
0
1
2
5
9
13
10

input
4
2 3
3 4
1 2
4 1

output
0
1
2
5