Giải bài trực tuyến

Given a sequence of N pairs of integers, find the length of the longest increasing subsequence of it.

An increasing sequence A₁..A_n is a sequence such that for every i < j, A_i < A_j.

A subsequence of a sequence is a sequence that appears in the same relative order, but not necessarily contiguous.

A pair of integers (x₁, y₁) is less than (x₂, y₂) if x₁ < x₂ and y₁ < y₂.

Input

The first line of input contains an integer N (2 ≤ N ≤ 100000).

The following N lines consist of N pairs of integers (x_i, y_i) (-10⁹ ≤ x_i, y_i ≤ 10⁹).

Output

The output contains an integer: the length of the longest increasing subsequence of the given sequence.

Example

Input:
8
1 3
3 2
1 1
4 5
6 3
9 9
8 7
7 6

Output:
3

Original problem: http://www.spoj.com/problems/LIS2/.