SPOJ Problem Set (classical)
2371. Another Longest Increasing Subsequence Problem
Problem code: LIS2

Given a sequence of N pairs of integers, find the length of the longest increasing subsequence of it.
An increasing sequence A_{1}..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_{1}, y_{1}) is less than (x_{2}, y_{2}) iff x_{1} < x_{2} and y_{1} < y_{2}.
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^{9} ≤ x_{i}, y_{i} ≤ 10^{9}).
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
