LIS2  Another Longest Increasing Subsequence Problem
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
Added by:  Bin Jin 
Date:  20080120 
Time limit:  0.345s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel Pentium G860 3GHz) 
Languages:  All except: C++ 4.9 SCM chicken 
hide comments
Chandrakanth :
20150612 11:08:45
Wrong answer test #1. Isn't the first test case the one given in the example itself?If it is then my program gives the correct output 3. Last edit: 20150612 11:10:17 

anando_du:
20150304 19:50:41
_ are u kidding with me !!! wrong ans#1 ? 

mkrjn99:
20141203 15:08:52
Binary search continues to amaze me! 

Sagar Shah:
20140526 19:04:28
How to do this problem???


Ghost Of Perdition:
20140127 12:55:15
N log^2 is getting TLE !!! 

Ravi Kiran:
20140102 10:27:09
My N * log^2 N implementation passed with 0.38s (in case you are skeptical about the time limit). 

ROHIT RAWAT:
20131028 07:14:13
Last edit: 20140112 19:24:24 

Ayush Nigam:
20130829 17:03:26
my O(nlogn) is giving tle!!! 

Mukit09:
20130802 20:04:23
Running...(4)


Bharath Reddy:
20130702 06:45:18
O(n^2) won't work..
