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
theph0enix: 2016-02-24 07:25:28

How do we compare (1, 3) and say (2, 3) since by the given definition of inequality these two pairs are neither less nor greater than the other. They cant even be considered equal since (1,3) is less than (2, 4) but (2, 4) is again neither less nor greater than (2, 3).

abhishekrahul: 2015-12-21 05:28:01

what it means TLE #3 ???

Last edit: 2015-12-21 05:38:40
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!


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