LIS2 - Another Longest Increasing Subsequence Problem

no tags 

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

An increasing sequence A1..An is a sequence such that for every i < j, Ai < Aj.

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

A pair of integers (x1, y1) is less than (x2, y2) iff x1 < x2 and y1 < y2.

Input

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

The following N lines consist of N pairs of integers (xi, yi) (-109xi, yi ≤ 109).

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

hide comments
sherlocklives: 2015-12-20 11:35:06

compilation error. compiling in system and ideone though :|

Dhawal Harkawat: 2015-11-06 06:54:37

AC..nlog^2n passes::D

epsilon: 2015-10-21 10:22:38

may someone plz tell me what it means:
"wrong answer #1"?

Vivek: 2015-07-23 13:29:06

nlogn solution : http://comscigate.com/Books/contests/icpc.pdf

santamaria: 2015-07-06 12:34:19

Check For This
3
-1 -2
3 -3
1 3

Chandrakanth : 2015-06-12 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: 2015-06-12 11:10:17
anando_du: 2015-03-04 19:50:41

-_- are u kidding with me !!! wrong ans#1 ?

mkrjn99: 2014-12-03 15:08:52

Binary search continues to amaze me!

Sagar Shah: 2014-05-26 19:04:28

How to do this problem???
Can anybody please give a hint??

Ghost Of Perdition: 2014-01-27 12:55:15

N log^2 is getting TLE !!!


Added by:Bin Jin
Date:2008-01-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP