SP2371 LIS2 - Another Longest Increasing Subsequence Problem

Given a sequence of $N$ pairs of integers, find the length of the **longest increasing subsequence** of it. An **increasing sequence** $A_{1},\dots,A_{n} $ is a sequence such that for every $i < j, A _{i} < A _{j}$. A **subsequence** of a sequence is a sequence that appears in the same relative order, but not necessarily contiguous. A pair of integers ($x_{1} , y _{1}$) is less than ($x _{2}, y_{2}$) **iff** $x _{1}< x _{2}$ and $y_{1} < y _{2} $ .

The first line of input contains an integer $N$ ($2 \leq N \leq 100000$). The following $N$ lines consist of $N$ pairs of integers ($x_{i}, y_{i}$)($-10^{9} \leq x_{i}, y _{i} \leq 10 ^{9} $).

The output contains an integer: the length of the longest increasing subsequence of the given sequence.