Hello, Codeforces!

Recently, I came across an interesting problem on SPOJ, and I would like your help in solving it:

Problem Statement:

You are given N (1 ≤ N ≤ 5000) intervals [L_i, R_i], where all intervals are different. Your task is to find the size of the largest subset of intervals that form a valid bracket sequence. This means that for any two chosen intervals in the subset, they must satisfy one of the following conditions:

1. They do not intersect, except possibly at their endpoints.
2. One interval is completely contained within the other.

Example:

Input

4

1 6
3 7
2 4
4 6

Output

3

Explanation:

We can choose intervals 1, 3, and 4, as they form a valid bracket sequence.