I. Best Friend, Worst Enemy
time limit per test
2 seconds
memory limit per test
32 megabytes
input
standard input
output
standard output

Bobo is analyzing a group of $$$n$$$ people, where the $$$i$$$-th $$$(1\leq i\leq n)$$$ person has two attributes, $$$ x_i $$$ and $$$ y_i $$$. The attribute values of different people are distinct. For any two persons $$$1\leq i,j\leq n$$$ ($$$i \neq j$$$), Bobo defines their friend index $$$\mathrm{Friend}(i,j)$$$ and enemy index $$$\mathrm{Enemy}(i,j)$$$ respectively as follows:

$$$$$$ \mathrm{Friend}(i,j) \triangleq \max(|x_i - x_j|, |y_i - y_j|), \quad \mathrm{Enemy}(i,j) \triangleq |x_i - x_j| + |y_i - y_j| . $$$$$$ For any $$$1\leq i,j\leq n$$$ ($$$i \neq j$$$), Bobo calls the $$$j$$$-th person is a best friend of the $$$i$$$-th person if $$$$$$ \text{ for all }1 \leq k \leq n\text{ }(k \neq i), \quad \mathrm{Friend}(i,k) \geq \mathrm{Friend}(i,j). $$$$$$

Also, for any $$$1\leq i,j\leq n$$$ ($$$i \neq j$$$), Bobo calls the $$$j$$$-th person is a worst enemy of the $$$i$$$-th person if $$$$$$ \text{ for all }1 \leq k \leq n\text{ }(k \neq i), \quad \mathrm{Enemy}(i,k) \leq \mathrm{Enemy}(i,j). $$$$$$

Now Bobo wants to find out, for each $$$1 \leq t \leq n$$$, how many ordered pairs $$$ (i, j) $$$ satisfy $$$ 1 \leq i, j \leq t $$$, $$$ i \neq j $$$, and the $$$j$$$-th person is both a best friend and a worst enemy of the $$$i$$$-th person if we only consider the first $$$t$$$ people.

Please be aware of the unusual memory limit.

Input

The first line contains one integer, $$$n$$$ ($$$2 \leq n \leq 4 \times 10^5$$$).

The next $$$n$$$ lines each contain two space-separated integers, where the $$$i$$$-th line contains $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq 10^7$$$). It is guaranteed that for $$$i \neq j$$$, either $$$x_i \neq x_j$$$ or $$$y_i \neq y_j$$$.

Output

Output $$$n$$$ lines, each line containing a single integer, denoting the number of pairs that meet the requirements.

Examples
Input
2
1 5
1 10
Output
0
2
Input
4
2 5
5 3
5 7
8 5
Output
0
2
4
4
Input
9
3 4
3 6
4 3
4 7
5 5
6 3
6 7
7 4
7 6
Output
0
2
1
0
4
5
6
7
8
Input
13
3 5
4 4
4 5
4 6
5 3
5 4
5 5
5 6
5 7
6 4
6 5
6 6
7 5
Output
0
2
4
7
2
2
5
2
2
3
3
4
4
Note

In the first example, when considering only the first person, there are no ordered pairs that meet the requirements. When considering the first two people, there are two ordered pairs that meet the requirements: $$$(1,2)$$$ and $$$(2,1)$$$.

In the second example, when considering only the first person, there are no ordered pairs that meet the requirements. When considering the first two people, there are two ordered pairs that meet the requirements: $$$(1,2)$$$ and $$$(2,1)$$$. When considering the first three people, there are four ordered pairs that meet the requirements: $$$(1,2)$$$, $$$(1,3)$$$, $$$(2,1)$$$, and $$$(3,1)$$$. When considering the first four people, there are four ordered pairs that meet the requirements: $$$(2,1)$$$, $$$(2,4)$$$, $$$(3,1)$$$, and $$$(3,4)$$$.