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
fr_sarker: 2023-11-24 10:53:33

helpfull Comment to solve this problem without segment tree:
link : https://www.quora.com/How-can-the-SPOJ-problem-LIS2-be-solved

albatroz: 2022-11-18 15:21:09

TL is too tight

hyl_tianmeng: 2021-07-24 05:24:30

你好

mahmud2690: 2018-04-20 17:03:30

2D-BIT >> 2D-Segment tree...

Md. Najim Ahmed: 2017-12-29 00:51:53

solved it n(log2n)^2 with 2d bit and grid compression ...

rihaz_zahir: 2017-02-01 16:08:51

@theph0enix, (1, 3) is not less than (2, 3), that all we care, even if (2, 3) comes before (1, 3) we would say (2, 3) is not less than (1, 3)

Last edit: 2017-02-01 16:11:23
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

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