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
Davit Safrastyan: 2016-12-10 18:41:46

Find the solutions of this problem in xoptutorials.com/spoj.php

rogerioagjr: 2016-07-21 03:28:19

TLE O(n*log(n)^2) :/

mkfeuhrer: 2016-06-29 22:11:58

dp gives tle !! LIS dp wont work!

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


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