Non-Intersecting Line Segments Placement

You are given an infinite number of Cartesian coordinate systems and N line segments. Each segment connects the points \( (X_{i,1},0) \) and \( (X_{i,2},H) \), where \(H\) is a positive constant (its value is not given and is not needed to solve the problem).

When two segments are placed in the same coordinate system, they are allowed as long as they do not intersect. In this problem, two segments \(i\) and \(j\) (with \(X_{i,1} < X_{j,1}\)) do not intersect if and only if \(X_{i,2} < X_{j,2}\). Your task is to determine the minimum number of Cartesian coordinate systems required to place all the segments without any intersection within the same system.

Hint: This is equivalent to partitioning the segments into as few chains as possible, where each chain contains segments sorted in increasing order of both \(X_{i,1}\) and \(X_{i,2}\). By Dilworth's theorem, the minimum number of chains equals the size of the largest antichain in the partial order.

inputFormat

The first line contains a single integer \(N\), the number of line segments.

Each of the following \(N\) lines contains two space-separated integers \(X_{i,1}\) and \(X_{i,2}\) representing the coordinates where the \(i\)-th segment starts and ends.

outputFormat

Output a single integer: the minimum number of Cartesian coordinate systems required to place all the segments such that no two segments in the same system intersect.

sample

3
1 2
2 3
3 4

1