You've just been paid and can't wait to spend it all at the world-famous casino, The World. Sadly, a world-famous casino comes with world-famous (long) lines to get in. Just as you get to the front of the line, a bunch of people cut in front of the you! Those jerks!

With nothing else to do, you find yourself staring at the backs of the line-cutters' heads. You notice something interesting: taller people block the view of anyone shorter in front of them. In other words, can only see someone if they are strictly taller than everyone behind them. So, every time someone cuts into the line, the number of people you can see will change.

Out of sheer boredom, you decide to keep track of how many people are visible in the line after each new person pushes in.

Input

The first line consists of an integer ~n~ ~(1 \leq n \leq 10^5)~, the number of people who enter the line.

Each of the next ~n~ lines contains two integers ~p_i~ and ~h_i~ ~(1 \leq p_i, h_i \leq 10^8)~:

• ~p_i~ is the position the person takes in line (larger ~p_i~ means further toward the front).
• ~h_i~ is the height of the person in centimeters.

People are added to the line in the order given — each one cuts into their specified position.

Output

For each person who enters the line, print a single integer, the number of people you can see after they join the line.

Clarifications

• You start with no one ahead of you in line.
• Everyone who joins the line will be in front of you. In other words, you are at position ~0~.

Example

Input 1

5
4 4
6 1
8 6
5 5
1 5

Output 1

1
1
2
3
2

• At position ~4~, someone ~4~ cm tall appears. You can see them.
• At position ~6~, someone ~1~ cm tall appears. You can't see them, because the person at position ~4~ is blocking them.
• At position ~8~, someone ~8~ cm tall appears. You can see them.
• At position ~5~, someone ~5~ cm tall appears. You can see them.
• At position ~1~, someone ~5~ cm tall appears. You can see them, but the block the people at position ~4~ and ~5~.

Here's a visual representation of this case. You are the blue person. The red people are people you can see.

Input 2

5
1 1
2 2
3 3
4 4
5 5

Output 2

1
2
3
4
5

Input 3

7
2 2
3 3
1 10
4 4
5 5
6 6
7 7

Output 3

1
2
1
1
1
1
1