Sphere Online Judge



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 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

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

hide comments
2014-12-03 15:08:52 Mayank Rajani
Binary search continues to amaze me!
2014-05-26 19:04:28 Sagar Shah
How to do this problem???
Can anybody please give a hint??
2014-01-27 12:55:15 Ghost Of Perdition
N log^2 is getting TLE !!!
2014-01-02 10:27:09 Ravi Kiran
My N * log^2 N implementation passed with 0.38s (in case you are skeptical about the time limit).
2013-10-28 07:14:13 ROHIT RAWAT


Last edit: 2014-01-12 19:24:24
2013-08-29 17:03:26 Ayush Nigam
my O(nlogn) is giving tle!!!
2013-08-02 20:04:23 Mukit Chowdhury
Running...(4)
Running...(9)
then wrong answer #1
What is this case ?? I've just used LIS in nlogn... Where am I doing wrong ???
2013-07-02 06:45:18 Bharath Reddy
O(n^2) won't work..
You have to do it in O(nlogn)
2013-04-05 15:10:13 Master Wad7a
@problem setter: can u please tell me whats wrong with my last submission?? ID:9044708. I tried a lot of test cases but couldn't find whats wrong.
2013-01-28 09:43:52 Ninja coder
@Sparik: All test cases. I doubt even 1 will pass :P
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.