406184: GYM102302 I Useless Pokemino

Laersh is a Pokemino trainer and he just captured his first pokemino. Throughout his journey he will capture more Pokeminos. Each Pokemino has an attack and a defense level. A Pokemino is better than another one if it has greater attack and greater defense level. Besides capturing Pokeminos, Laersh can breed any two Pokeminos that he owns and generate a new Pokemino. This new Pokemino's attack and defense will be a linear combination of its parents attributes:

Attack_child = Attack_parent1 * c + Attack_parent2 * (1 - c)

Defense_child = Defense_parent1 * c + Defense_parent2 * (1 - c)

The number c is the same for attack and defense, and can be any number 0 ≤ c ≤ 1.

An useless Pokemino is a Pokemino such that Laersh owns a better Pokemino, or he can breed a better Pokemino. For each new Pokemino that Laersh captures, help him figuring out the number of useless Pokeminos that he owns.

The first line of the input contains one integer N (1 ≤ N ≤ 10⁵). N lines will follow. The i-th line will contain two integers A_i (0 ≤ A_i ≤ 10⁹) and D_i (0 ≤ D_i ≤ 10⁹) each. A_i represents the attack of Pokemino i and D_i represents the defense of Pokemino i. Note: No two captured Pokeminos will have the same attack and defense.

Output N numbers, the i-th number represents how many useless Pokeminos there are when the i-th Pokemino is captured.

10
10 0
10 1
10 2
9 3
8 4
7 4
3 4
2 4
1 4
0 4

0
0
0
0
0
0
0
0
0
0

5
3 6
6 4
6 9
7 2
10 8

0
0
1
2
3