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
Huỳnh Quang Thảo: 2011-07-20 12:11:07

I think this problem same as LIS. But I AC and has wrong answer, anyone help me why ?

Graphis_: 2011-07-17 03:58:28

Administrator:My program works fine on my computer.I succeded in compiling it using G++ 3.4.5,4.3.4,4.4.2,and 4.5.2.
Yet on your sever I always get CE.
Here is your report.

g++: Internal error: File size limit exceeded (program as)
Please submit a full bug report.
See for instructions.
For Debian GNU/Linux specific bug reporting instructions, see
.

Hy Trường Sơn: 2011-07-17 03:58:28

nice problem!

Eric Alejandro Destefanis: 2011-07-17 03:58:28

I cant sleep... i cant get this problem out of my head haha, any little hints? (apart from using LIS)


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