Minimizing Preparation Time of Stick Processing

You are given n sticks. Each stick has a length l and a width w. A machine processes these sticks one by one. Before processing the first stick, the machine requires a preparation time of 1 minute. For every subsequent stick with dimensions \(l_i\) and \(w_i\), if the previous stick processed had dimensions \(l\) and \(w\) such that \(l \geq l_i\) and \(w \geq w_i\), then no additional preparation time is needed. Otherwise, the machine requires an extra 1 minute preparation time.

In other words, if you can partition the sticks into groups where, within each group, you can arrange the sticks in an order such that every consecutive pair \((l, w)\) and \((l_i, w_i)\) satisfies \(l \geq l_i\) and \(w \geq w_i\), then the total preparation time will be equal to the number of groups (since the first stick in each group costs 1 minute).

Your task is to determine the minimum total preparation time required to process all n sticks by choosing an optimal processing order.

Mathematical Formulation:

Let the sticks be given by \((l_1, w_1), (l_2, w_2), \dots, (l_n, w_n)\). You need to find the minimum number of chains (groups) such that for every chain \((l_{i_1}, w_{i_1}), (l_{i_2}, w_{i_2}), \dots, (l_{i_k}, w_{i_k})\) we have:

[ \begin{aligned} l_{i_1} &\geq l_{i_2} \geq \cdots \geq l_{i_k}, \ w_{i_1} &\geq w_{i_2} \geq \cdots \geq w_{i_k}. \end{aligned} ]

The answer is the minimum number of such chains required.

inputFormat

The first line contains an integer (n) ((1 \leq n \leq 10^5)). Each of the next (n) lines contains two integers (l) and (w), representing the length and width of a stick.

outputFormat

Output a single integer representing the minimum total preparation time required (i.e. the minimum number of groups into which the sticks can be partitioned).

sample

5
4 9
5 2
2 1
3 5
1 4

2