"Nested rectangles"

Let’s consider a sequence of rectangles a_1×b_1, a_2×b_2, …, a_N×b_N. For each j, a_{j }≤ b_j. Rectangles cannot be rotated. Rectangle a_i×b_i can be put inside rectangle a_k×b_k iff (a_{i }< a_k) and (b_{i }< b_k). We call sequence of rectangles nesting sequence, iff each rectangle can be put inside following one.

Your task is to write a program that finds the longest nesting subsequence, i. e. the longest nesting sequence among all subsequences of the given sequence.

Input

The 1^st line of input data contains the number of rectangles N (1 ≤ N ≤ 100000). Each of the following N lines contains two integers a_i b_i (1 ≤ a_{i }≤ b_{i }≤ 10^9) — size of i-th rectangle.

Output

Output exactly one integer number — the length of the longest nesting subsequence.

Examples