Buildings need an overall structure to be maintained; they cannot rely on the foundation alone... — LazyJazz

[Halloween Party in progress...]

LazyJazz has called on everyone to build a block tower together, a super-tall block tower. Everyone first conceived a final goal, which is the shape of the final tower, and then planned to divide the work to build several smaller block towers. Each small block tower corresponds to a certain segment of the final tower's structure, and finally, they are stacked one by one.

The final form of the block tower consists of $n$ blocks of uniform density and equal height, with equal width but varying lengths, stacked on top of each other with their widths aligned. From top to bottom, the $i$-th block covers the horizontal range $[L_i, R_i]$ (inclusive of both $L_i$ and $R_i$), with a length of $R_i - L_i$ units. Based on the description above, it can be concluded that the mass of each block is proportional to its length.

Since it is a block tower, the tower may be unstable. The stability condition is: if a block tower has $m$ layers, it is stable if and only if for any $i \in [1, m)$, the center of mass of the first $i$ blocks (from top to bottom) falls within the coverage range of the $(i+1)$-th block. Otherwise, it is unstable. The center of mass of the first $i$ blocks is the geometric center of the first $i$ blocks, which is the weighted average position using mass as the weight.

For example:

A 3-layer block tower, from top to bottom, the first layer covers $[1, 3]$, the second layer covers $[0, 2]$, and the third layer covers $[1, 2]$. Its structure is stable.

.##
##.
.#.

A 3-layer block tower, from top to bottom, the first layer covers $[1, 3]$, the second layer covers $[0, 2]$, and the third layer covers $[0, 1]$. Its structure is unstable (even if every two layers are stable when viewed separately).

.##
##.
#..

A 3-layer block tower, from top to bottom, the first layer covers $[0, 8]$, the second layer covers $[4, 12]$, and the third layer covers $[5, 7]$. Its structure is stable (even if the bottom two layers look unstable).

########....
....########
.....##.....

LazyJazz wants to build the tower well while avoiding unstable structures during the intermediate process (i.e., each small block tower that the final tower is decomposed into must be stable, and all intermediate forms when stacking the small block towers one by one must also be stable). Therefore, you are needed to help plan how to decompose the final structure into small block towers, ensuring that the maximum number of layers in any small block tower is minimized. You only need to output the minimum possible value for the maximum number of layers in a small block tower after decomposition.

Input

The first line contains a positive integer $n$, representing the total number of layers in the final block tower.

The next $n$ lines each contain two non-negative integers $L_i, R_i$, representing that the $i$-th layer from the top covers the range $[L_i, R_i]$.

It is guaranteed that the block tower structure given in the input is stable.

Output

A single positive integer representing the minimum possible value of the maximum number of layers in a small block tower among all feasible decomposition schemes.

Examples

Input 1

3
1 3
0 2
1 2

Output 1

1

Note 1

This example corresponds to the first example in the problem description. It can be seen that even if the blocks are stacked one by one, no unstable structure appears.

Input 2

3
0 8
4 12
5 7

Output 2

2

Note 2

This example corresponds to the third example in the problem description. The optimal scheme is: from top to bottom, the first two layers are divided into one small block tower, and the last layer is divided into another small block tower.

Input 3

5
3 13
3 13
0 8
4 12
7 8

Output 3

3

Note 3

The structure is shown below:

...##########
...##########
########.....
....########.
.......#.....

The optimal scheme is: from top to bottom, the first three layers are divided into one small block tower, and the last two layers can be divided or not.

Input 4

See sample data download.

Output 4

See sample data download.

Input 5

See sample data download.

Output 5

See sample data download.

Subtasks

For some reasons, this problem uses bundled testing. Each subtask contains several test cases and is divided into 4 subtasks. You will only receive the points for a subtask if you pass all test cases within that subtask.

$0 \leq L_i < R_i \leq 10^4$

It is guaranteed that the block tower structure given in the input is stable.