Jeongol wants to store boxes in a warehouse. There are $N$ boxes numbered from $1$ to $N$. Box $i$ ($1\le i\le N$) has size $s_i$ and storage capacity $c_i$. Every box has capacity smaller than its size: $c_i<s_i$.

Thinking that too many boxes make the warehouse cluttered, Jeongol wants to put boxes inside other boxes. The following conditions must hold:

• A box can contain a box whose size is at most its storage capacity.

• A box already containing another box may itself be placed inside another box.

• Each box may directly contain at most one box. In other words, at most one other box may be placed inside a box, but that other box may itself contain further boxes.

The storage cost is the number of boxes that are not contained in any other box.

For example, consider $N=4$ and the following sizes and capacities:

If box 4 is put inside box 1, and box 1 inside box 3, as shown below, two boxes are not contained in other boxes, so the storage cost is 2.

However, placing boxes 2 and 4 inside box 3 as shown below violates the conditions, because box 3 directly contains two boxes.

Not all boxes have to remain in the warehouse. Jeongol plans to keep only some boxes with the smallest numbers and discard the rest. Jeongol has not yet decided how many boxes to use.

Help Jeongol by writing a program that, for every $i$ from $1$ to $N$, computes the minimum cost of storing boxes $1,2,\ldots,i$.

Constraints

• All given numbers are integers.
• $2\le N\le2\times10^5$.
• $1\le c_i<s_i\le10^9$ ($1\le i\le N$).

Subtasks

1. (7 points) $N\le6$.
2. (12 points) $s_i=c_i+1$.
3. (26 points) $N\le1000$.
4. (17 points) $s_i\le100$.
5. (38 points) No additional constraints.

Input

The first line contains the number of boxes $N$.

The next $N$ lines, starting from the second line, describe the boxes. The $i$-th of these lines contains the size $s_i$ and storage capacity $c_i$ of box $i$, separated by a space.

Output

Print $N$ lines.

On line $i$ ($1\le i\le N$), print the minimum cost of storing boxes $1,2,\ldots,i$.

Examples

Input 1

4
6 4
5 1
9 8
2 1

Output 1

1
2
2
2

Input 2

6
3 2
5 4
3 2
4 3
4 3
3 2

Output 2

1
1
2
2
2
3

Input 3

8
13 6
7 5
9 4
11 10
4 2
15 5
16 7
8 3

Output 3

1
2
3
3
3
4
4
5