B. The Best Wife
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Sofia is the best wife, and she constantly comes up with new ideas on how to spend time with her husband. Idea $$$i$$$ could be described by a segment $$$[l_i..r_i]$$$. It means Sofia wants to visit some event that starts at day $$$l_i$$$ and ends at day $$$r_i$$$. If she decides to visit an event, she fully commits to it and is there every day from $$$l_i$$$ to $$$r_i$$$ inclusive.

Sofia can't visit more than one event each day. Also, if some event ends on day $$$d$$$ and another event starts on day $$$d$$$, she can only visit one of them.

After each new idea comes to her mind, she wonders what the biggest number of events she could visit.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of ideas.

Each of next $$$n$$$ lines contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 6 \cdot 10^5$$$) — description of the $$$i$$$-th idea.

Output

For each $$$i$$$ in a range $$$1..n$$$, print one integer — the maximum number of events out of $$$1, 2, ..., i$$$ that Sofia can visit.

Example
Input
5
1 3
3 5
1 2
5 6
4 4
Output
1
1
2
2
3